Response Length Perception and  Sequence Scheduling: An LLM-Empowered LLM Inference Pipeline
Authors: Zangwei Zheng
Xiaozhe Ren
Fuzhao Xue
Yang Luo
Xin Jiang
Yang You
Venue: NeurIPS 2023 poster (2023)
Keywords: large language models
inference optimization
batch processing
TL;DR: We propose an efficient large language model (LLM) inference pipeline that leverages LLMs' response length perception ability for sequence scheduling, resulting in an 86% increase in inference throughput.

Abstract: Large language models (LLMs) have revolutionized the field of AI, demonstrating unprecedented capacity across various tasks. However, the inference process for LLMs comes with significant computational costs. In this paper, we propose an efficient LLM inference pipeline that harnesses the power of LLMs. Our approach begins by tapping into the potential of LLMs to accurately perceive and predict the response length with minimal overhead. By leveraging this information, we introduce an efficient sequence scheduling technique that groups queries with similar response lengths into micro-batches. We evaluate our approach on real-world instruction datasets using the LLaMA-based model, and our results demonstrate an impressive 86% improvement in inference throughput without compromising effectiveness. Notably, our method is orthogonal to other inference acceleration techniques, making it a valuable addition to many existing toolkits (e.g., FlashAttention, Quantization) for LLM inference.

Response Length Perception and Sequence Scheduling: An LLM-Empowered LLM Inference Pipeline
Zangwei Zheng', Xiaozhe Ren?, Fuzhao Xue', Yang Luo', Xin Jiang", Yang You'
*Department of Computer Science, National University of Singapore
Noah's Ark Lab, Huawei.
Zznggwei, f-xue, yangluo, youy) @wwom..ussceu...g..... (renxiaozhe, jiang.xin) @ huawwi..com
https://githine com/ httpa/bbwwo//eeeggggggg/ggeeeeee http:///Seeuueec--c-ccllllaaaa
Abstract
Large language models (LLMs) have revolutionized the field of AI, demonstrat- ing unprecedented capacity across various tasks. However, the inference process for LLMs comes with significant computational costs. In this paper, we propose efficient LLM inference pipeline that harnesses the power of LLMs. Our ap- proach begins by tapping into the potential of LLMs to accurately perceive and predict the response length with minimal overhead. By leveraging this informa- tion, we introduce an efficient sequence scheduling technique that groups queries with similar response lengths into micro-batches. We evaluate approach real-world instruction datasets using the LLaMA-based model, and our results demonstrate impressive 86% improvement in inference throughput without compromising effectiveness. Notably, our method is orthogonal to other inference acceleration techniques, making it valuable addition many existing toolkits (e.g. FltshAttention, Quantization) for LLM inference.
Introduction
Large language models (LLMs) [2, 6, 15, 19] have transformed the field natural language pro- cessing (NLP) and have demonstrated remarkable success in various NLP tasks such as language translation [23], question-answering [28], and text summarization [38]. However, the deployment of LLMs scale poses challenges due to their prohibitively expensive inference cost [1, 27]. The computational resources required to process millions of queries, as is the case with currently deployed LLMs like ChatGPT [19], are substantial. As a result, reducing the inference cost of LLMs has become a crucial research direction in recent years.
In real-world scenarios, the lengths of responses to various queries exhibit significant variability. As depicted in Figure Figure 2a, although different models display slightly diverse response length distributions, common pattern emerges with the presence of response lengths across wide range. Consequently, when performing large language model (LLM) inference in batches, the inclusion of sequences with differing response lengths leads inefficiencies. Shorter sequences for longer ones to complete, resulting in computational waste. This issue is depicted on the left side of Figure Figure 1, where redundant tokens account for a substantial portion (66%) of the overall tokens generated. Given the quadratic time complexity of inference, such inefficiencies impose significant burden on the inference process.
forced to wait
Humans possess the ability to estimate the length of an answer to a question based on their understand- ing of the query. For instance, questions like "What the capital of France?" typically elicit shorter responses compared to inquiries such as "Can you explain the history of the French Revolution?" Intriguingly, we observe that LLMs fine-tuned for instruction comprehension, such ChatGPT and Claude, also exhibit certain degree of response length perception. Moreover, even smaller models
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Instruction
Response
Instruction
Predicted Length
Response
66%
2
Resporse Length Percaption
2
4
Sequence Scheduling
3
16%
Fallure Collection
Wining prediction
6
Variable mirco-belich size according to length
Mottibbtthh Instruction
Resporse length
Restandant computatio
Fallures from other microbatiche
Recompusation
Figure I: Left: Vanilla batch inference leads to underperformance with 66% redundant tokens when short and long responses are in the same batch. Right: The pipeline of our sequence scheduling. First, the response length perception module estimates the response length for each instruction. Sequence scheduling groups instructions with similar predicted lengths together and larger batch sizes for shorter responses. Failure collection and recomputation strategy is adopted to avoid wrong predictions degenerating the performance.
ChatGPT
500
3000
Vicuna
2500
Response Length
400
Frequency
2000
300
200
1000
100
500
100
200
300
400
500
200
400
600
800
1000
Response Length
Data Point
(a) Response length distribution 10k instruc- tions from ChatGPT and Vicuna. Response lengths larger than 512 are truncated.
(b) Distribution of mean length among times generations on Ik instructions. Error bar denotes maximum and minimum length in generations,
Figure Distribution of response length and variance. The response length is measured tokens.
like LLaMA-7B, when instruction-tuned on a length prediction dataset, acquire this capability. Despite the variability in output length under multiple sampling, as demonstrated in Figure Figure 2b, these models achieve impressive performance in perceiving the length of their responses.
Leveraging the response length perception ability of LLMs, we can employ to enhance the scheduling of instructions within micro-batches. This represents example of software-hardwan co-design, where the inherent capabilities L.LMs contribute to the acceleration of the LLM inference process. Our proposed sequence scheduling system intelligently groups queries based on their perceived response lengths, effectively minimizing computational waste. To further improve efficiency, introduce failure collection and recomputation strategy, well as variable batch size approach. These additional techniques complement the sequence scheduling system and contribute to further improvements in inference throughput.
In order evaluate the effectiveness of our proposed approach, we conduct experiments on real- wol-w instruction datasets using Vicuna [4], an instruction-tume -tuned LLaMA model [34]. Our length predictor module surpasses the performance of previous methods accurately estimating response lengths. Our sequence scheduling system demonstrates remarkable improvement in inference throughput, achieving an 86% increase compared to the original inference process, while maintaining perfor- mance quality. These results highlight the potential of sequence scheduling with response length

---

perception as a valuable addition to the existing toolkit (e.g. Flash Attention [7]. Quantization [8, 11, 35]) for large language model inference.
To summarize, our contributions are as follows:
We investigate the response length perception ability of LLMSs and demonstrate that instruc- tion tuning can enhance this capability.
We introduce novel LLM inference pipeline called sequence scheduling that leverages LLMs' response length perception. This approach intelligently groups queries with similar response lengths, reducing computational waste and improving inference throughput without compromising performance.
We present comprehensive experimental results on real-world instruction datasets using the Vicuna-7B model. Our proposed method achieves an impressive 86% improvement in inference throughput compared to the original inference process.
2
Related Work
Large Language Model As-a-service. Large Language Models (LLMs) [2, 6, 15, 19] have been successful in building strong foundation models by scaling language models to a large scale. With instruction tuning [25], LLMs can align with human requirements and provide them
service for practical usage. Currently, LLMs such as ChatGPT [19] and PaLM [6] have been deployed in Bing and Bard service and perform a significant amount of inference every day. Therefore, reducing the inference cost of LLMs is a crucial research direction.
Efficient LLM Inference. In recent years, there has been increasing interest in developing efficient inference techniques for large language models (LLMs) [18]. Kernel fusion [5, involves the use of highly optimized kernels to reduce memory access and improve computation speed. Parallelism methods, such as pipeline parallelism [17, 30] and tensor parallelism [22, 30], have been used to distribute the workload across multiple GPUs, enabling efficient scaling of LLM inference. Quantization [8, 11, 35] has also been explored as a means of compressing the parameters of LLMs for efficient inference. In addition to these methods, there has been some work on optimizing batch processing for LLMs [3, 10, 29]. For example, [3] focused on batchifying queries in few-shot settings, while [10] proposed grouping sentences into batches based on input length. For LLM, the cost of generation exceeds the forward of prompts. Our method focus on the generation process and group sentences according to the predicted output length.
Response Length Prediction. The previous work on response length prediction has primarily focused on non-autooregressive generation (NAR) translation tasks [14]. In these tasks, the entire sentence is generated at once, so predicting the length of the response is crucial. Various techniques have been proposed address this problem. For instance,
[32] proposed a simple approach based on the statistics of the dataset and a bias term, while [13] predicted the number of tokens each input token would be translated into. Some methods, such [9, 12]. added a special [LENGTH] token to the encoder, while others, such as [20, 21, 24, 31]. used pooling layer and MLP classifier to predict the response length based on the encoder's outputs. However, these methods are primarily applicable to machine translation tasks, where the target sequence length is similar to the source length and thus casier to predict. In contrast, our proposed approach is specifically designed for large language model inference tasks, where the types of queries and their corresponding response lengths vary widely.
Response Length Perception
3.1 Perception in Advance (PiA)
Instruction-tuned LLMs have shown the ability to align with human understanding and provide helpful and safe responses. Interestingly, we have found that these models possess an overall understanding of the entire response they are going to generate, similar to how humans formulate their responses. In our experiments, we asked these models to predict the length of the responses they were about to generate, even though explicit task for response length perception included during pretraining.
3

---

Table Examples of generation with Perception in Advance (PiA). Instruction-leamedd models are able to follow the PiA instruction. Small models (Vicuma) may fail to generate the response.
Prompt:
Create a fun math question for children.
Before responding to the above instruction, you have to predict the length of your response. Print the estimated number of words in your response in the lirst line. Then change to new line to respond to the instruction.
GPT-4:
Estimated response length: 60 words.
Sure, here's fun math problem: There are 7 apples in busket. A friendly squirrel comes and
ChatGPT:
4 words
If you have 10 apples and give your friend, how many do you have left? <BOS>
Claude:
225
Here a fun math question for children: Jenny the Juggler was practicing her act. one hand she held
Vicuna:
101 <EOS>
Table 2: Performance of response length perception via Perception in Advance across different LLMs.
Perception in Advance (PiA)
Perception Only (PO)
Error(w)
Acc-50
Acc-100
Error(w).
Acc-50
Acc-100
Failure
GPT-4
22
80%
100%
100
28%
55%
0%
ChatGPT
51
77%
90%
89
55%
68%
2%
Claude
37
64%
96%
63
52%
84%
0%
Bard
70
44%
72%
130
28%
50%
28%
HugginChat-3Bae
52%
72%
113
56%
72%
12%
Vicuna- 13B
49%
73%
92
55%
75%
Vicuna-7B
123
40%
65%
122
40%
65%
0%
As shown in Table 1, we introduce modification to the original prompt by including an instruction to estimate the response length in advance. We refer to this method as Perception in Advance (PiA). We applied this modified prompt various LLMs and observed their responses to the instruction.
Comprehension of Response Length. Our experiments demonstrate that instruction-tune tuned LLMs possess strong comprehension of response length estimation when provided with the PiA in- structions. To evaluate the effectiveness of the PIA method, we conduct tests using 175 alpaca seed instructions [33]. The results, shown in Table 2, indicate that GPT-4, ChatGPT, and Vicuna successfully followed the instructions for all queries.
One interesting aspect we discovered during our analysis is that LLMs exhibit a better understanding of words compared tokens. This observation aligns with how humans comprehend and generate responses. By considering words as the unit of measurement, we can obtain more reliable estimates of response length.
To quantitatively evaluate the accuracy of response length perception, we employed the metric Error(w), which measures the difference between the estimated number of words and the actual word number. We also consider two thresholds for accuracy: Acc-50 and Acc- 100, where a prediction is considered correct if the difference falls below 50 and 100 words, respectively. Our analysis reveals that both GPT-4 and Claude exhibited exceptional performance in response length estimation. They achieve an error of fewer than 50 words and demonstrate an Acc-100 score exceeding 90%. These results demonstrate the high accuracy and reliability of the response length predictions generated by these models. Furthermore, it worth noting that models with a higher number of parameters exhibit superior performance in response length prediction.
Side Effect of PiA on Response Generation. Introducing EiA has side effect on the response generation process. First, since the estimated length is visible to the model during the generation phase, can influence how the model generates responses. The model can perceive the estimated

---

Table 3: Response length perception performance comparison: we evaluate different prediction methods for vicuna model inference length on 10k instructions.
Error +
Acc-50 1
Acc-100 f
GPT-2 (1.5B)
Pooling + MLP [LEN]-token Fine-tune
127
35%
53%
92
43%
64%
LLaMA-7B
Pooling + MLP [LENN]ttken Fine-tune
127
35%
53%
81
46%
70%
Vicuna-7B
Pooling + MLP
73
55%
75%
[LEN]-token Fine-tune
84
47%
72%
Perception Only
193
38%
59%
Instruction Tuning
63
56%
81%
length as constraint and attempt to tailor its response to fit the predicted length. This behavior can be seen as a length-limited generation.
To investigate the impact of PiA on response generation, we compared the error in response length perception between the PiA method and the Perception Only (PO) method. In this case, compare the response length of unmodified instructions with the perceived length values. Note that the response length can vary across different sampling generated from the same instruction. Figure 2b illustrates the variability in response length for 1,000 data points, highlighting the wide range of possible lengths. As result, there is no definitive "ground truth" for response length but rather range of possible lengths. To simplify the estimation task, we aim for the model to predict the maximum potential length, as using the mean length has limitations, discussed in the subsequent section.
For smaller LLMs, such as Vicuna 7B and 13B, observed that they almost ignore the estimated length. On the other hand, GPT-4 and Claude demonstrate a stronger tendency to tailor their answers fit the estimated length, resulting in significantly smaller error numbers.
In addition, we observed that introducing the PiA method might negatively impact the response quality for smaller LLMs. For instance, in the case of Vicuna-7B, we notice instances where the model failed to generate a response after predicting the length. This behavior can be attributed to the limited capacity of smaller LLMs to handle multiple tasks simultaneously.
Perception Only is Harder. In order to address the side effects associated with response generation influenced by estimated length, we adopt Perception Only (PO) style for sequence scheduling since decouples the prediction and generation processes.
One straightforward approach to perform PO employ the prompt but solely retrieve the length prediction. We then compare this estimated length with the actual response generated using the original prompts. As presented in Table 2, it is evident that although LLMSs still capable of estimating the length, their eтror rates are significantly higher, and accuracy scores are lower compared to the Perception in Advance (PiA) approach.
3.2 Instruction Tuning
While the Perception in Advance approach may be sufficient for GPT-4 in terms of small side effects on the generation process and enabling sequence scheduling, we aim to completely decouple the prediction and generation stages to avoid any potential influence of the estimated length. Additionally, we want to empower smaller models with the ability to accurately perceived response lengths. To achieve these objectives, employ instruction tuning [25]]
During the instruction tuning phase, we utilize modified prompt format that prompts the model to predict the length of the response instead of generating the entire response. We select subset of 10,000 prompts from the alpaca dataset [33]. We sample four generations for each prompt and set the target length the maximum one. The target text is number only, so the generation cost
5

---

2.4
Throughout IsamplesiS
0.8
Throughput (sampl esess
2.2
2.0
0.6
1.8
1.6
0.2
max new tokens: 512
1.4
stop when finished
16
32
64
16
32
64
128
256
512
1024
Batch Size
Group Size
(a) When generating fixed length (blue), through- put grows almost lincarly. When generating until finishing a hatch, long response large batch size degrades performance.
(b) Larger group size makes scheduling more ef- fective. Scheduling fails when the group size too small (32). The improvement more instructions in group decreases as group size grows.
Figure Throughput vs. batch size and group size.
in the prediction process is minimized. To optimize the training process and reduce computational resources, we employ the efficient training method LoRA [16]. which requires negligible memory compared with the LLM, and train the model for three epochs. For further details on the experimental setup, we provide comprehensive information in the appendix section of this paper.
Table 3 presents the experimental results, showcasing the improvement achieved through instruction tuning. The prediction eлrоr is greatly reduced from 193 to 63, and Acc-50 shows an improvement of 18%. We also compare our instruction tuning approach with previous length prediction methods utilized in NAR generation, such as fine-tuning with length token and employing an MLP to classify pooled hidden states. Although these methods also exhibit performance improvements, they fall short compared to the effectiveness of instruction tuning. These results highlight the model's 's ability to comprehend and effectively utilize the provided instruction. Furthermore, when using alternative models such as LLaMA-7B or smaller models like GPT-2 to generate length predictions for Vicuna, the pooling + MI.P approach fails completely, and fine-tuning with a length token falls short when compared to Vicuna's is self- eeff-rrediction capabilities.
4 Sequence Scheduling
4.1 Method
Having established an accurate response length perception module, now leverage it to enable sequence scheduling for efficient inference. As illustrated in the left side of Figure when instructions with highly disparate response lengths are batched together, significant, redundant computations occur, resulting in reduced inference throughput. Therefore, by grouping instructions with similar response lengths together,
accelerate the inference process.
Before delving into the specifics of sequence scheduling, is important to understand the significance of inference with large micro-batch sizes (mbs). As depicted in the Figure 3a, deploying Vicuna on an 80GB A100 GPU highlights the benefits of larger batch sizes leveraging the parallel computing power of the GPU. When generating fixed number of tokens for each sample, the throughput exhibits almost linear improvement up to batch size 16. after which the rate of improvement slows down. On the other hand, if the generation of each batch halts when all samples have finished generating their responses, the throughput also increases linearly for batch sizes smaller than 16, with higher ratio than the fixed-token approach. However, as the batch size continues to increase, performance begins to decline. This is due to the fact that larger batch sizes have a high probability of entailing longer response length, resulting in significant redundant computations.
To enable efficient sequence scheduling, we make the assumption that the number of instructions to process at time (group size) is larger than the micro-batch size for single GPU, which holds true given the widespread usage of L.MMs. While a straightforward approach sequence scheduling to sort the instructions by their predicted length and split them into batches for processing,

---

mbs=1
70ms
64ms
64ms
70ms
64ms
64ms
mbs=16
220ms
69ms
69ms
69ms
Instruction processing
Generating one taken
Vanilla
9%
91% %
Ours
16%
14%
70%
Instruction processing
Response Length Prediction
Response Generation
Time comparison between instruction processing and token generation. Instruction processing only takes time to generate a few tokens. Bottom: Percentage distribution bar for different components of vanilla and our methods.
Figure 4: Top:
explore additional designs further accelerate throughput. The pipeline of our method depicted on the right side of Figure 1.
Failure Collection and Recomputation (FCR) Although the length predictor achieves reasonably high accuracy of 81% %1% (ace-100), there is still a chance that some samples have predictions that deviate significantly from the true response length. These incorrect predictions can greatly disrupt the efficiency of batch processing. For example, a long response is mistakenly predicted as short one and included in a batch with predominantly short responses, the overall processing time is affected as the short queries are forced to wait for the completion the long one. To mitigate this issue, we implement a mechanism called Failure Collection and Recomputation (FCR). We restrict the number of newly generated tokens to be at most the maximum predicted length within a batch. Any instruction that exceeds this predicted length is considered failure and is collected separately for further recomputation the end of a group size inference process. Given the relatively low failure ratio, this approach enables faster generation of shorter responses with limited time spent regenerating failed instructions.
Variable Batch Size (VBS) One important consideration in sequence scheduling is memory usage during response generation. Shorter responses require less memory compared to longer ones. However, we allocate larger batch size without considering the possibility of misclassified long responses short ones, we might encounter out-of-memory errors. With the help of Failure Re- collection, we introduce the Variable Batch Size (VBS) technique. We allocate larger batch size for shorter responses. A simple rule is to maintain the same number of tokens in each batch. Given the baseline batch size By corresponding to a specific length Ly, we adjust the batch size based on the desired length L using the formula Be L/1L This approach optimizes memory usage by allowing larger batch sizes for shorter responses while preventing memory overflow caused by RC.
Binning and Predicting the Max Length training the length predictor, we employ a binning strategy that categorizes the target length into bins. In our approach, we use bins with cell size of 50 and round the numbers to the nearest bin that is greater than the actual length. First, the objective of predicting the bin number is simpler and casier it requires only approximate estimation. Second, binning provides a buffer for potential errors in length prediction. Even if the actual length deviates within the same bin, it does not impact the effectiveness of our methods.
In addition, we choose to predict the maximum length four times the generation process because the consequences of underestimation are more severe compared to overestimation. By predicting the maximum length, we ensure that the generated responses have enough capacity to accommodate even the longest possible output. Predicting the mean length, on the other hand, would result in higher failure re-collection ratio, as it may underestimate the length for some queries, leading to potential disruptions in the batching process.
Overhead of Length Prediction Given that we must predict the lengths of all instructions within a group before generating their responses, there an inherent overhead associated with response length prediction. This overhead entails calculating the keys and values for the instruction tokens and generating small number of tokens (typically 2 to tokens). However, as depicted in Figure 4, the processing time for instructions is extremely fast, requiring only the time to generate few tokens
7

---

Table 4: Performance of sequence scheduling with different response length perception module.
Throughput (samples/s) f Improvement
Tokens/batch +
Vanilla
1.22
377
Ground Truth Preditor
2.52
+107%
201
Pooling + MLP
1.96
+61%
216
[LEN]-token Fine-tune
2.10
+72%
210
Perception Only*
1.40
+15%
328
Instruction Tunning (mean)
1.77
+45%
211
Instruction Tunning (max)
2.27
+86 %
208
Table 5: Ablation study on three components of sequence scheduling method.
Binning
FCR
VBS
Throughput (samples/s) 1 Improvement
Tokens/batch +
1.73
+42%
271
1.76
+44%
222
2.22 V
+82%
209
X
1.58
+30%
300
V
1.86
+52%
209
2.27
+86 %
203
(ranging from to tokens). Consequently, this overhead can be effectively offset by the overall acceleration achieved through sequence scheduling.
4.2 Experiments
Experimental Setting. Our experiments conducted two datasets: set of 10,000 prompts from subset of the alpaca dataset [33] (which is different from the one used to train the length predictor) and set of 429 prompts from the Instruction-in-Vine Wild datasets [36]. The former consists of self-instructed prompts, while the latter contains real-world collected prompts.
For our baseline experiments, set the batch size to 16. Regarding the variable batch size strategy. we use a batch size of 16 for instructions with a length (L) greater than or equal to 300. For instructions with length below 300, then round it to the nearest power of 2 for better GPU utilization. We maintain a fixed group size of 256. The inference is performed on the Vicuna-7B BB| [4] model using 80GB A100 GPU. We sample generations with a temperature of 0.5 for diversity in responses.
calculate the batch size using the formula 256x50/L and
We evaluate the throughput at the sample level and report the number of samples processed per second and the corresponding improvement compared the vanilla baseline, where inference conducted with batch size 16. The average length refers to the mean length of each batch, where smaller average length indicates reduced redundant computation.
Results. Table 4 presents the performance of sequence scheduling with different response length perception modules. Among the length predictors considered, the one with instruction tuning demonstrates the best performance, achieving an impressive 85% improvement in throughput. The acceleration due to smaller number tokens per batch, which includes wasted tokens due to short sentences waiting for the long ones to be completed. It important to note that the estimation-only method exhibits a significantly higher failure re-collection ratio, resulting in reduced performance. Hence, we report the results obtained using the vanilla sequence scheduling approach.
When predicting the mean length, the failure re-collection ratio increases to 29.8%, which consid- erably higher compared to the 15.3% achieved when predicting the maximum length. Consequently. performance improvement drops to 45%. Alternatively, if we utilize the ground truth (i.e., maximum length observed during multiple inferences) as the length predictor, it serves as upper bound for this method. Our approach performs only 0.25 samples/s slower than the upper bound, showcasing that effective length predictor can yield substantial improvements.

---

Table 6: Performance of sequence scheduling on Instruction-in -nn- Wild dataset.
Throughput (samples/s) 1
Avg. length +
Error
Acc-50
Acc-100 1
Vanilla Estimation Only
0.78
475
1.07
422
358
20%
38%
Instruction Tunning
1.24
299
139
43%
68%
Table 7: Study on the Failure Collection and Recomputation (FCR) ratio.
k
Avg. Wait
Max. Wait
FCR ratio
FCR time
Throughput (samples/s)
-50
42%
63%
34%
21%
1.80
-10
37 %
53%
20%
20%
2.10
37%
52%
15%
20%
2.27
+10
45%
52%
14%
14%
2.20
+50
38%
55%
7%
7%
2.10
Furthermore, our method exhibits low variance in throughput, with a value of 0.05 over three times experiments. This indicates the stability and consistency of our approach in achieving improved inference speed.
Table 5 presents an ablation study on the three components of our approach, demonstrating their indi- vidual contributions the overall improvement. We observe that Binning enhances the effectiveness of Variable Batch Size (VBS), leading to a more powerful combination. Fach component plays a significant role in achieving the final improvement in throughput. Furthermore, Table 6 showcases the performance of our methods on the Instruction-in- Wild dataset, confirming the effectiveness of our approach across different datasets.
In addition, on the right side Figure 3b, we analyze the relationship between throughput and group size. We observe that a larger group size provides more flexibility for sequence scheduling, resulting in improved throughput. However, the rate of improvement gradually slows down as the group size increases. Thus, becomes crucial strike balance between the overhead involved in gathering the group size information in real-world scenarios and the achieved improvement.
Waiting time. Apart from the throughput, another important metric the waiting time for each user. We introduce three metries for comparison: maximum waiting time, average waiting time, and their ratio (maximum waiting time multiplier). The maximum timing time is fairness metric for measuring individual request delay. We define the waiting time for receiving the request (start of processing group) to generate the corresponding response. With group size 256, our method saves 63% average waiting time compared the vanilla. Due to the FCR mechanism, our maximum waiting time multiplier is 2.7, which is 1.4 times the vanilla's one. However, with inference speed acceleration, the maximum wait time also reduced by 48%.
be the delay from
FCR ratio. One factor influencing inference latency the Failure Collection and Recomputation (FCR) ratio. This ratio represents the proportion of FCR samples recalculated at the end of batch, which causes delays in processing. To assess the effect of different FCR ratios, we modify predicted length by constant value k. A larger predicted length results in lower FCR ratio (more tolerable). However, a long response with a short predicted length may introduce more waste generation in batch (generating A more times). The experimental results are as shown in Table 7. The Avg. Wait and Max. Wait columns denote the the average and maximum wait times compared to the vanilla method. FCR time indicates the proportion of time utilized for FCR processing.
When using an accurate length predictor, is advisable to directly utilize the predicted length with 15% FCR ratio. This approach strikes a balance between the time spent on FCR recomputation and the time wasted during batch computation. few more tokens to complete the task, but it is difficult to determine which response will finish or if will finish even after generating more tokens. This concern is also the reason why the maximum length among four times generation is used, as it aims to reduce the potential FCR ratio.
some cases, generation process might require just

---

Limitation and Discussion
One limitation is that accurate response length prediction not always guaranteed, even with the instruction-tunet length predictor module we developed. While our experiments demonstrate promising results, there still room for improvement in the accuracy of response length estimation.
Besides, although sequence scheduling significantly reduces redundant computations, it cannot completely eliminate the issue. Even with ground truth response length predictor, the ratio of redundancy decreases from 66% to 33%, leaving ample room for further improvement. Recent works such ORCA [37] have proposed novel inference systems that offer alternative solutions to mitigate the redundant computation problem.
Another limitation of our work is that we focus less on the process of input instructions. As the maximum token length supported by LLMs increases, users may input very long instructions, leading to redundant computations and inefficiencies. Future work could explore combination of our proposed sequence scheduling with input batch scheduling techniques, such as those discussed in Fang et al. (2021) [10], further optimize the inference process.
Our approach assumes that the group size exceeds the capacity of a single GPU. As large language models may become a ubiquitous infrastructure, similar to search engines, the number of queries will increase significantly. Furthermore, the emergence of models like GPT-4 with 32k sequence length support and Claude with 100K sequence length support amplifies the challenge of handling varying response lengths, highlighting the relevance and effectiveness of our method.
Our approach is easily extensible to multi-GPU settings, where multiple GPUs are used for faster processing and handling larger model sizes. By reallocating batches of sequences with different perceived response lengths to different GPU nodes, our method remains effective in high- high-performance computing environments. This extension ensures scalability and maintains the efficiency gains achieved in our approach.
Some argue method needs reorder inputs. However, the order of sequences is critical; rather, the focus is on batch assembly. If requests in group arrive together, the overhead from reordering indices is negligible. The main latency arises from the response length perception, not index reordering. After forming batches, their processing order is flexible. Although this might affect individual user latency, it's bound by group's processing time. Batch shuffling can also offset order impacts. In multi muUti-GPU setups, batches with varied predicted response lengths are sent to different GPUs for simultaneous processing, emphasizing batch assembly over sequence order.
For more powerful LLMs (such as GPT-4, Claude, etc.), our proposed PiA method introduces no need for instruction-tunning and introduces overhead during sechennc---ceduling..... This can better handle long inputs and multi-turn conversation. However, as these models are not open-sourced, is unable to perform experiments on them. Detailed dicussion on PiA method can be found in appendix C.
Our findings indicate that large language models (LLMs) possess comprehensive comprehension of their generated responses. This understanding opens up possibilities for the creation of faster inference techniques, including -on-autoregressive methods, that overcome the performance constraints associated with sequential token generation.
Conclusion
In this paper, we proposed novel technique called sequence scheduling, which optimizes large language model (LLM) inference by leveraging response length prediction. Our approach groups queries with similar response lengths in batches, reducing computational waste and improving inference throughput. We introduced the concepts of failure re-collection and variable batch size to further enhance efficiency. Experimental results on real-world instruction datasets using the Vicuna-7B model demonstrated an 86% improvement in throughput without sacrificing performance quality. Our method offers a valuable addition to the existing toolkit for LLM inference, addressing the challenge of efficient deployment of LLMs at scale.
10

---

Acknowledgements
Yang You's research group is being sponsored by NUS startup grant (Presidential Young Professor- ship), Singapore MOE Tier-1 grant, ByteDance grant, ARCTIC grant, SMI grant and Alibaba grant. This work sponsored by Huawei Noah's Ark Lab. We would like thank Shenggan Cheng and Ziming Liu for their valuable discussion, including advice on the implementation.
References
[1] R. Y. Aminabadi et al., "Deepspeed inference: Enabling efficient inference of transformer models unprecedented scale," arXiv preprint 0rX0v:2207.00332, 2022.
[2] T. Brown al., "Language models are few-shot learners," Advances neural information
processing systems, vol. 33. pp. 1877-1901, 2020.
[3] Z. Cheng. J. Kasai, and T. Yu, "Batch prompting: Efficient inference with large language model apis," arXiv preprinl arXiv:2301.0872 2023.
[4] W.-L. Chiang et al., Vicuna: An open-source chatbot impressing gpt-4 with 90% * chatgpt quality, Mar. 2023. [Online]. Available: https: /msys. org / blog/ 2023 03 30 vicuna/.
[5] J. Choi, H. Li, B. Kim, S. Hwang, and J. H. Ahn, "Accelerating transformer networks through recomposing softmax layers," in 2022 IEEE International Symposium on Workload Character- ization (ISSC)), IEEE, 2022, pp. 92-103.
[6] A. Chowdhery et al., "Palm: Scaling language modeling with pathways." arXiv preprint
arXiv:2204.022 023311, 2022.
[7] T. Dao. D. Fu, S. Ermon, A. Rudra, and C. Ré, "Flashattention: Fast and memory-efficient exact attention with io-awareness," Advances in Neural Information Processing Systems, vol. 35,
pp. 16344-16 359, 2022.
[8] T. Dettmers, M. Lewis, Y. Belkada, and I.. Zettlemoyer, "I.m.int8(:: 8-bit matrix multiplication for transformers at scale," arXiv preprint arXiv:2208.07535 2022.
[9] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, "Bert: Pre-training of deep bidirectional transformers for language understanding," arXiv preprint 1rXiv::810. 04805, 2018.
[10] J. Fang, Y. Yu, C. Zhao, and Zhou, "Turbotraanstomeers: An efficient gpu serving system for transformer models," in Proceedings of the 26th ACM SIGPLAN Symposium Principles and Practice of Parallel Programming. 2021, pp. 389-402.
[11] E. Frantar, S. Ashkboos, T. Hoefler, and D. Alistarh, "GPTQ: Accurate post-training compres- sion for generative pretrained transformers." " arXiv preprint "xXiv2220.173222 2022.
[12] M. Ghazvininejad, Levy, Liu, and Zettlemoyer, "Mask-predict: Parallel decoding of conditional masked language models," arXiv preprint 1rXiv:1904.09324, 2019.
[13] J. Gu, Bradbury, C. Xiong, O. Li, and R. Socher, "Non-autoregresssvve neural machine translation," arXiv preprint arXiv: 1. 000281, 2017.
[14] J. Gu and X. Tan, NNon-autoregressive sequence generation," in Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics: Tutorial Abstracts, 2022.
pp. 21-27.
[15] J. Hoffmann al., "Training compute-optimal large language models," arXiv preprint
xrxi:2203.155333
2022.
[16] E. J. Hu et al., "Lora: Low-rank adaptation of large language models," arXiv preprint arXiv:2100 1et.22.666.0.6.... 2021.
[17] Huang el al., "Gpipe: Efficient training of giant neural networks using pipeline parallelism."
Advances in neural information processing systems, vol. 32, 2019.
[18] S. Kim al., "Full stack optimization of transformer inference: A survey," arXiv preprint arXiv:2302. /4017, 2023.
[19] A. Koubaa, "Gpt-4 vs. gpt-3.5: A concise showdown." " 2023.
[20] J. Lee, E. Mansimov, and K. Cho, "Deterministic non-autoregressive neural sequence modeling by iterative refinement," arXiv preprint wrXiv:1802.0690) 2018.
[21] Lee, R. Shu, and K. Cho, "Iterative refinement in the continuous space for non-autoregresssve neural machine translation." arXiv preprint arX1v:2009.07177,, 2020.

---

[22] S. Li et al., "Colossal-ai: A unified deep learning system for large-scale parallel training," arXiv preprint arXiv:2110.14883, 2021.
[23] C. Lyu, J. Xu, and L. Wang. "New trends machine translation using large language models:
Case examples with chatgpt," arXiv preprint wxXi:2305.00/181, 2023.
[24] X. Ma, C. Zhou, X. Li, G. Neubig, and E. Hovy, "Flowseq: Non-autoregressive conditional
sequence generation with generative flow," arXiv preprint arXiv:
2019.
[25] L. Ouyang et al., "Training language models to follow instructions with human feedback," Advances in Neural Information Processing Systems, vol. 35, pp. 27 230-27 744, 2022.
[26] A. Paszke et al., "Automatic differentiation in pytorch." 2017.
[27] R. Pope et al., "Efficiently scaling transformer inference," arXiv preprint arXiv:2211.05100,
2022.
[28] J. Robinson, C. M. Rytting, and D. Wingate, "Leveraging large language models for multiple
choice question answering," arXiv preprint arXiv:2210.122 12353, 2022.
[29] Y. Sheng al., thrigh-throughput generative inference of large language models with single gpu," arXiv preprint ar arXiv:2303.06%
2023.
[30] M. Shoeybi, M. Patwary, R. Puri, P. LeGresley. J. Casper, and B. Catanzaro, "Megatron-Im Training multi-billion parameter language models using model parallelism," arXiv preprint arXiv: 000500 2019.
[31] R. Shu, J. Lee, H. Nakayama, and K. Cho, "Latent-variable non-autoregressivv neural machine translation with deterministic inference using a delta posterior," in Proceedings of the aaai conference artificial intelligence, vol. 34, 2020, pp. 8846-8853
[32] Z. Sun, Z. Li, H. Wang. D. He, Z. Lin, and Deng. "Fast structured decoding for sequence models," Advances in Neural Information Processing Systems, vol. 32, 2019.
[33] R. Taori et al., Stanford alpaca: An instractionnfoolloiigg Ilama model, https: : / github. lab/ s stanf ord_aadddo alpaca, 2023.
[34] H. Touvron el al., "Llama: Open and efficient foundation language models," arXiv preprint
arXiv:2302. /3971, 2023.
[35] Wu, C. Li, R. Y. Aminabadi, Z. Yao, and Y. He, "Understanding int4 quantization for transformer models: Latency speedup, composability, and failure cases," arXiv preprint
arXiv:2301. /2017, 2023.
[36] F. Xue, K. Jain, M. H. Shah, Z. Zheng, and Y. You, Instruction in the wild: A user-based instruction dataset, https: htop::://gii
t/gttbbb/bbbbt.g./. thub. cww/ conn/XueFuzzarn www.ee//wwaa///ttttttttoiooooooa InstructionWild, 2023.
[37] G.-I. Yu. J. Jeong, G.-W. Kim, S. Kim, and B.-G. Chun, "Orca: A distributed serving system for { (ranssormerr-ased)) generative models," in 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22), 2022, pp. 521-538.
[38] T. Zhang, F. Ladhak, E. Durmus, P. Liang, K. McKeown, and B. Hashimoto, "Benchmarking large language models for news summarization." arXiv preprint arXiv:2301. 13848. 2023.
12

---

Appendix
A Additional Instruction Tuning Implementation Details
To fine-tune the instruction-tunee length predictor module, followed specific procedure. First, we prepared the dataset by sampling each instruction four times. One sample was obtained using greedy decoding with temperature of 0, while the other three samples were generated using temperature of 1.0 with different random seeds. The maximum length among the four samples was used the target length for each instruction.
For the training dataset, we constructed new instructions by appending the requirement of perceiving the response length only. The prompt used for this purpose was: "Don't output the response for the above instruction. Instead, you need to predict the number of tokens in your response. Output only one number."
During the training process, we employed the same hyperparameters the Vicuna [4] instruction tuning process on LLaMA [34]. Specifically, we set the learning rate to 0.00005 and trained the model for three epochs. We applied the LoRA [16] method solely to the query and key linear layer. The training was conducted on single 80GB A100 GPU. All codes are implemented in PyTTrcch [26].
B Distribution of Instruction-in-Ve Wild Dataset
The histogram of response length Instruction-in in- Wild [36] dataset is shown in Figure 5. The response length is more diverse and contains more responses with a long length.
30
Vicuna
Freguency
20
15-
10
5-
100
200
500
Response Length
Figure 5: Response length distribution Instraction-in-WWe Wild dataset.
Discussion on Sequence Scheduling with PiA
In the main text, we presented the sequence scheduling technique using instruction-tume models, where the LoRA weight utilized for response length perception. However, recent LLMs such as GPT-4 and Claude have shown promising performance in Perception in Advance (PiA), which allows them to leverage PiA for sequence scheduling without the need for additional weights.
To understand the PiA process, consider the following format:
[Input] [PiA Prompt] [PiA Response] [Response]
Here, the PiA prompt might be something like "Please estimate the length of your prediction," and the subsequent PiA Response could be "The estimated response length is [X]". The primary overhead of this method involves the generation of the aforementioned tokens, typically more than 30 in number.
As stated section 3.1, PiA may have different behaviour than Perception Only (PO) because the response now depend on PiA prompt and response. Howver, we can eliminate this effect due the fact that the input and the response can be detached from the PiA Prompt and its Response.
13

---

To ensure the quality of the response remains unchanged, we can use the following two methods:
After the generation of the PiA response, we can exclude both the PiA Prompt and PiA Response embeddings. The generation of the primary Response would then only use the kv-cache of the input.
Alternatively, the Response can be generated with both the PiA Prompt and PiA Response masked.
Both these strategies ensure the preservation of generation quality, In our experiments with models like ChatGPT and other leading-edge Large Language Models (LLMs), merely invoking the API didn't allow for the bypassing of the PiA prompt's influence. However, this implementation is quite simple for the companies. This observation also led us to introduce the Perception Only (PO) approach, wherein we compared the mean predicted length against the original prediction length as an estimation of performance of PiA method in practice.
To further improve the speed of inference in this setting, one potential approach is to reuse the key-value (kv) cache of imput queries from the response length perception stage during the inference stage. This eliminates the need for recomputing the kv-cache input instructions, thereby saving valuable processing time.
One strategy we explored is offloading the kv-cache to the main memory and then loading it back into the GPU memory. However, the transfer time between the CPU and GPU can be significant and greatly impact overall performance, often surpassing the time saved by recomputation. To address this, one possible improvement is to offload and load only a portion of the kv-cache asynchronously, reducing the transfer time overhead. This is an area that we leave for future work and exploration.
Another approach investigated involved compressing the kv-cache and storing it directly in the GPU memory. We applied FlexGen's 's quantization method [29] for compression and found that it had minimal impact on performance. However, this approach does consume additional memory and can lead to a smaller batch size, potentially degrading overall performance. A potential avenue for further exploration is combine compression and offloading techniques to strike balance between memory usage and performance.
Considering these factors, have chosen to continue using the recomputation strategy for the PiA response length perception module in our proposed pipeline. While there is potential for optimizations through offloading and compression, further investigation and refinement are required to achieve substantial performance gains in practice.
14


Reviews:
[{"review_id": "uciH7SCOnV", "reviewer": "Reviewer_KzBJ", "summary": "The authors propose to improve the throughput of the LLM inference systems by correctly predicting the length of the response. \n\nMethod summary: \n1. Predict the length of the response (Binning length for prediction modules to learn better)\n2. Use the prediction to batch the queries with similar prediction to improve throughput (use variable batch size to leverage GPUs while managing memory requirements) \n3. Failure collection module to cut-off mispredicted batch evaluation. To ensure that this module is not triggered too often, it is advisable to over-estimate length of the prediction\n", "questions": "Comments:\n1. For table two to make sense, it would be useful to have some data statistics like distribution of response lengths on those 175 instructions. \n2. Table 3 caption can be improved a lot. It was not clear what i am looking at first. The table talks about vicuna model inference and various prediction methods for that. Elaborate on the caption.\n\nQuestions:\n1. In table 4. why is the vanilla avg length significantly different from other lengths including ground-truth predictor?\n", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper tackles an important problem, provides a simple recipe for the solution and works reasonably well.\n2. The evaluation is to the point. Answers all the natural questions that might arise.", "weaknesses": "The writing can be better. Some details in the questions section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the insightful comments. We are pleased to see that the reviewer acknowledges our contribution. The questions are answered below.\n\n**Question-1**: We appreciate the reviewer's clarification on the 'Avg. length' metric. Indeed, the metric does not means the average length of the generated response but rather measures the average token generation. The latter one includes wasted tokens due to short sentences waiting for the long one to be completed. In fact, since we do not change the model, with a same random seed, the response for a specific prompt under different inference acceleration methods (including vanilla, ground-truth predictor and ours) is the same and so is the response length. Therefore, a smaller Avg. length means less waste in token generation and better performance. The vanilla Avg. length is much worse than the ground-truth predictor because it has a poor performance. We will change the 'Avg. length' metric to 'Tokens wasted' metric for better understanding.\n\n**Comment-1**: The distribution of response lengths between ChatGPT and Vicuna is given in Figure 2.(a) which can be a reference. \n\n**Comment-2**: We acknowledge the need for a clearer caption for the table. In the revised version, we will modify the caption to read \"Response length perception performance comparison: we evaluate different prediction method for vicuna model inference length on 10k instructions.\""}, {"review_id": "Xk5ECrv8T9", "reviewer": "Reviewer_WTWP", "summary": "This paper comes up with the technique of using LLM to help LLMs’ inference to be more efficient. It predicts the queries’ response length, and group the those with similar response length into the same micro-batch, so that the inference efficiency can be effectively improved.", "questions": "Imaging a scenario that a user’s query has extreme long response length predicted, would this user wait long time for the response? \nHow about to use a small model to learn to predict the response length?\n", "limitations": "None.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "In the experiments, the proposed method gains significant improvement in terms of inference speed.\nIt is reasonable that the token redundancy leads to inefficient inference in batch.\nIt is effective and easy to implement for existing LLMs.\n", "weaknesses": "The metric of horizontal axis in Fig. 2 (a) is missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the insightful comments. We are pleased to see that the reviewer acknowledges our contribution. The questions are answered below.\n\n**Question-1**: No matter how extreme length is predicted (we can also assume a worst case: this sample actually gets a very short response), the sample is processed within a group of group size 256 in our experiment. This means the wait time for a user is bounded. We measured that our methods save 63% average waiting time for all users and 48% for the longest waiting users. Although the relative waiting time for the worst case is enlarged by 40% w.r.t. the average waiting time, our method's acceleration makes the real waiting time less for **all** users.\n\nIn addition, in a group, we dispatch different samples into batches and the execution order of the batches can be shuffled, which means a sample with extreme length predicted may not be the last one for computation. The situation is even better in a multi-gpu situation. The sequence scheduling only assembles batches and the batches can be processed by different GPUs at the same time. Thus, a wrongly predicted response length will not lead to long time waiting.\n\nUsing a small model can be a tradeoff between response length prediction overhead and wasted tokens saved. In Table 4, we show Pooling + MLP can improve by 61%, which is 25% lower than using the instruction-tuned model. In Table 3, a smaller model (GPT-2) achieves worse performance than the Pooling + MLP and thus may not yield better performance.\n\n**Weakness-1**: The metric of horizontal axis is \"token\" for Fig. 2(a) and we will add it in the revision."}, {"review_id": "wNFzz7BMdh", "reviewer": "Reviewer_u5zm", "summary": ">**Rebuttal:** The provided details satisfy my concerns. I think this paper should be accepted after applying the agreed changes.\n\n>**TL;DR:** The paper presents a new technique to reduce the inference time of LLMs under intensive usage. This is an important problem that can reduce wasteful computations. However, the paper is missing some key comparisons and the experimental methodology is lacking justifications. Addressing my concerns and questions would improve my score.\n\nThis paper proposes a new to reduce the inference time of LLMs under intensive usage. The technique save wasteful computations by predicting the response length and aggregating similar predicted lengths together. The paper presents an inference pipeline, which is composed of response length prediction, failure collection and recomputation (FCR), and variable batch size (VBS).\n\nExperimental results on real-world instruction datasets using the Vicuna-7B model demonstrated an 86% improvement in throughput without sacrificing performance quality. The datasets include the Instruction-in-Wild and Alpaca. The proposed technique is compared to previous works and outperforms them on both datasets.", "questions": "* **Q.1.** The paper describes several LLM use cases such as ChatGPT, Bard, and Claude. These chat-bots require support for multi-turn conversations, which expands the conversation history. How would the proposed technique work in such cases?", "limitations": "The limitations of the proposed technique are described throughout the paper. The limitations include overhead of length prediction and poor compatibility with long inputs. However, the latency effects of waiting for the aggregation of batches is not discussed or evaluated.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* **S.1.** The proposed technique can reduce inference time of LLMs and gain a 86% performance improvement.\n* **S.2.** The paper tackles an important problem of reducing the LLM inference time and wasteful computations.\n* **S.3.** The proposed technique outperforms previous compared works on two datasets.\n* **S.4.** Reproduction code is provided as part of the submission.", "weaknesses": "* **W.1.** Th paper lacks comparison to existing LLM inference works such as [1][2].\n* **W.2.** Some the key technique attributes are not well justified. For example, the target length prediction is four times the actual length. No experiments or ablations are provided to justify the \"four\". Another example is the FCR mechanism, which immediately stops the generation process when the maximum predicted length has been surpassed. There might cases where the generation process might only need a few more tokens to complete the task.\n* **W.3.** The proposed technique relies on very short inputs in order to be effective. This is rarely the case for chat-bot, which require support for multi-turn conversations and are given as the examples for LLM usage. Furthermore, the proposed technique relies on high LLm usage to create batches of similar predicted lengths. This high usage is typically found in chat-bots.\n\n\n[1] Yu, Gyeong-In, Joo Seong Jeong, Geon-Woo Kim, Soojeong Kim, and Byung-Gon Chun. \"Orca: A distributed serving system for {Transformer-Based} generative models.\" In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22), pp. 521-538. 2022.\n\n[2] Pope, Reiner, Sholto Douglas, Aakanksha Chowdhery, Jacob Devlin, James Bradbury, Jonathan Heek, Kefan Xiao, Shivani Agrawal, and Jeff Dean. \"Efficiently scaling transformer inference.\" Proceedings of Machine Learning and Systems 5 (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the insightful comments. We are pleased to see that the reviewer acknowledges our contribution. The questions are answered below.\n\n**Weakness-1**: One significant strength of our method is its compatibility with various existing toolkits. In [2], the proposal involves selecting the best multi-dimensional partitioning techniques optimized for TPU v4 slices, which focuses on operator-level improvements and is orthogonal to our method.\n\n[1] introduces the Orca system, which selectively applies batching only to a few operations instead of processing an entire batch of requests by \"batchifying\" all tensor operations comprising the model. In comparison, our method is more scalable as it does not split operations and can achieve better performance with a larger group size. Moreover, our approach is simpler to implement and can be integrated into the existing inference pipeline without the need for a completely different inference system like Orca. Additionally, our method can be combined with Orca for potential further improvements.\n\n**Weakness-2**: The term \"four times\" might be misunderstood. It refers to the process of generating the response for each request four times and then selecting the maximum length among the four generated responses (the reason for choosing the maximum instead of the mean is explained in line 225). This process is not about predicting a target length four times the actual length. Instead, the predicted length is determined by the predictor, and the length prediction for each request is dependent on the specific sample.\n\nTo relieve the concern of FCR mechanism, we modify the predicted length by a constant value 'k'. A larger predicted length (more tolerable) results in a lower FCR ratio. However, a long response with a short predicted length may introduce more waste generation in batch (generating 'k' more times). We can view the FCR ratio as a tradeoff between the above-mentioned two factors. The experimental results, as shown in the table, demonstrate the average and maximum wait times (Avg. and Max) compared to the vanilla method, with FCR time indicating the proportion of time utilized for FCR processing.\n\n| k   | Avg. | Max | FCR ratio | FCR time | Throughput (samples/s) |\n| --- | ---  | --- | --------- | -------- | ---------- |\n| -50 | 42%  | 63% | 34%       | 21%      | 1.80       |\n| -10 | **37%**  | 53% | 20%       | 20%      | 2.10       |\n| 0   | **37%**  | **52%** | 15%       | 20%      | **2.27**       |\n| +10 | 45%  | 52% | 14%       | 14%      | 2.20       |\n| +50 | 38%  | 55% | 7%        | 7%       | 2.10       |\n\nWhen using an accurate length predictor, it is advisable to directly utilize the predicted length with a 15% FCR ratio. This approach strikes a balance between the time spent on FCR recomputation and the time wasted during batch computation. In some cases, the generation process might require just a few more tokens to complete the task, but it is difficult to determine which response will finish or if it will finish even after generating more tokens. This concern is also the reason why the maximum length among four times generation is used, as it aims to reduce the potential FCR ratio.\n\n**Weakness-3**: We recognize that high LLM usage is essential for creating batches with similar predicted lengths in chat-bot inference. However, our method does not assume anything about the input length, and long inputs do not significantly impact our approach. In Fig. 4, we observe that the processing time for inputs (only one forward pass) is relatively small compared to the response generation process, which remains the bottleneck for chat-bot inference due to token-by-token generation and multiple forwards.\n\nDespite the Instruction-in-Wild dataset containing long length requests, our method still manages to improve throughput compared to the vanilla approach. Additionally, we acknowledge the limitation discussed in line 288 and believe that further enhancements can be made in input length scheduling. Nevertheless, we emphasize that the input processing is not the bottleneck for the chat-bot; it is primarily the response generation process that poses the greatest computational challenge.\n\n**Question-1**: In multi-turn conversations, predicting the response length for each turn is feasible based on the conversation history. The method used depends on how the conversation history is saved. If only texts are preserved with key-value (kv) keys dropped, it becomes a long input request, and it can be directly handled. On the other hand, if the system keeps the kv-cache, offloading, and compression techniques (as discussed in supplementary section C) can be employed to achieve faster responses. To further enhance the approach, implementing strategies such as limited window size and input length scheduling shows promise as future work.\n\n**Limitation**: We show the Avg. and Max waiting time compared to the vanilla method. We define the wait time for a user to be the delay from receiving the request (start of processing a group) to generate the corresponding response. With group size 256, our method saves 63% average wait time compared to the vanilla. Due to the FCR mechanism, our max wait multiplier is 2.7, which is 1.4 times the vanilla's one. However, with inference speed acceleration, the max wait time is also reduced by 48%."}, {"review_id": "mrHfbIg8qE", "reviewer": "Reviewer_Nixu", "summary": "The authors propose a simple method to perceive the length of an LLM response by asking the LLM. Then, the authors propose to groups queries with similar response lengths into micro-batches, which are then allocated to different GPU nodes and processed in parallel . The authors show empirical gain in terms of throughput. This approach is also orthogonal to other inference acceleration approaches. ", "questions": "I have listed my concerns above.", "limitations": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed method is simple and exact and does not sacrifice response quality while achieving speedup. \n\n2. The authors show impressive speedup in terms of throughput.\n\n3. The speed up the author achieve can be applied on top of other inference acceleration techniques.", "weaknesses": "1. One fundamental weakness of the paper lies in the assumption that requests can be reordered, which may not hold in production. The author did not show any fairness metric which may help readers understand how their method affect each individual request in practice.\n\n2. The author did not show any fine-grained ablation studies examining how often and how often the requests have been reordered and how it affects inference latency.\n\nI would happily raise my rating if the authors can present more thorough ablation studies. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the insightful comments. We are pleased to see that the reviewer acknowledges our contribution. The questions are answered below.\n\n**Weakness-1**: The foundation of our method is not based on the assumption that individual requests can be \"reordered,\" but rather on the expectation that a \"group\" of requests is received simultaneously (as mentioned on line 192). In real-world production environments, big companies such as OpenAI and Google, the volume of requests is substantial and continues to increase over time. For instance, in April, ChatGPT handled approximately 1.7 billion requests, resulting in an average request rate of nearly 700 per second. This exceeds the scale of our experimental setup, where the group size was set at 256. Conversely, smaller companies with a limited number of requests can opt for stream inference instead of batch processing. Our method will become increasingly critical as AI technology continues to advance and become more widespread.\n\nWe think a fairness metric for measuring individual request delay is very important. We introduce three metrics for comparison: max wait time, average wait time, and their ratio (max wait multiplier). We define the wait time for a user to be the delay from receiving the request (start of processing a group) to generate the corresponding response. With group size 256, our method saves 63% average wait time compared to the vanilla. Due to the FCR mechanism, our max wait multiplier is 2.7, which is 1.4 times the vanilla's one. However, with inference speed acceleration, the max wait time is also reduced by 48%.\n\n**Weakness-2**: Our method emphasizes that the order of requests is not a crucial factor. The key lies in how we assemble batches. Assuming that requests in a group arrive simultaneously, reordering the index has minimal additional overhead. The main inference latency is primarily influenced by the perception of response length rather than the reordering of indices.\n\nOnce batches are formed, we can process them in any order. While the order of batch processing may affect the latency for individual users in our setup, the latency is constrained by the processing time of a group. Batch shuffling can be employed to mitigate any order-related impact. In a multi-GPU environment, batches containing different predicted response lengths are dispatched to different GPUs and processed simultaneously. In this scenario, there is no explicit ordering; it is solely about batch assembly.\n\nOne factor influencing inference latency is the Failure Collection and Recomputation (FCR) ratio. This ratio represents the proportion of FCR samples recalculated at the end of a batch, which causes delays in processing. To assess the effect of different FCR ratios, we modify the predicted length by a constant value 'k'. A larger predicted length results in a lower FCR ratio (more tolerable). However, a long response with a short predicted length may introduce more waste generation in batch (generating 'k' more times). The experimental results, as shown in the table, demonstrate the average and maximum wait times compared to the vanilla method, with FCR time indicating the proportion of time utilized for FCR processing.\n\n| k   | Avg. | Max | FCR ratio | FCR time | Throughput (samples/s) |\n| --- | ---  | --- | --------- | -------- | ---------- |\n| -50 | 42%  | 63% | 34%       | 21%      | 1.80       |\n| -10 | **37%**  | 53% | 20%       | 20%      | 2.10       |\n| 0   | **37%**  | **52%** | 15%       | 20%      | **2.27**       |\n| +10 | 45%  | 52% | 14%       | 14%      | 2.20       |\n| +50 | 38%  | 55% | 7%        | 7%       | 2.10       |\n\n"}]

Author rebuttal:

Meta-review: The paper initially received mixed reviews. The authors' rebuttal addressed concerns that reviewers raised. The proposed idea seems to simple and effective. By predicting the response length first, the proposed method can group queries with similar output lengths to increase LLM inference throughput. All reviewers agreed that this is a good and potentially practically useful. It is expected that authors integrate the promised changes to the final version of the paper.
Decision: Accept (poster)