PaperlayerView exact revision on arXiv

Source-linked AI summary

Response Length Perception and Sequence Scheduling: An LLM-Empowered LLM Inference Pipeline

Zangwei Zheng, Xiaozhe Ren, Fuzhao Xue, Yang Luo, Xin Jiang, Yang You

arXiv:2305.13144v2cs.CL

TL;DR

LLM inference is costly, and variable response lengths make batched processing inefficient. This paper predicts response lengths to group queries into micro-batches, yielding an 86% throughput increase over original inference while maintaining performance quality.

  • Problem

    LLM inference is costly at scale, and variable response lengths make batched inference inefficient because shorter sequences wait for longer ones.

    Source: §1 · p. 1

  • Method

    The pipeline predicts response lengths to group queries of similar lengths into micro-batches, complemented by failure collection and recomputation and variable batch sizes.

    Source: §1 · p. 2

  • Results

    86% improvement in inference throughput over the original inference process, while maintaining performance quality.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Response-length-based sequence scheduling is a valuable addition to the existing toolkit for LLM inference.

    Source: §1 · p. 2

    33% redundancy remains with a ground-truth response length predictor, down from 66%, so sequence scheduling does not eliminate redundant computation.

    Source: §5 · p. 9

Abstract

from arXiv · show

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.

1 Introduction

LLM inference is costly [1] [27], and varied response lengths make batched inference wasteful. The paper uses LLM response-length perception to schedule similar-length queries together and improve throughput.

1 Introduction

  • When short and long responses share an inference batch, shorter sequences wait for longer ones, and redundant tokens account for 66% of tokens generated.The paper motivates reducing inference costs because deploying LLMs at scale requires substantial computational resources [1] [27].Source: §1 · p. 1
  • Instruction tuning can enhance LLM response-length perception, and length-tuned LLaMA-7B can acquire this capability despite output variability under multiple sampling.Instruction-tuned models including ChatGPT and Claude also show some response-length perception.Source: §1 · pp. 1–3
  • Sequence scheduling groups queries with similar perceived response lengths into micro-batches to reduce computational waste, complemented by failure collection and recomputation and variable batch sizes.The pipeline is presented as complementary to existing inference toolkits such as Flash Attention and Quantization [8] [11] [35].Source: §1 · pp. 2–3
  • 86% higher inference throughput than the original inference process, with performance quality maintained, on real-world instruction datasets using Vicuna.The length predictor also surpassed previous methods in accurately estimating response lengths.Source: §1 · p. 2

2 Related Work

The related work frames inference-cost reduction as important for deployed LLM services and positions the method against prior inference optimizations and response-length predictors developed for other tasks.

Large Language Model As-a-service

  • Scaling and instruction tuning produced capable, human-aligned LLM services, including ChatGPT and PaLM [6] in Bing and Bard, motivating inference-cost reduction.The cited foundation models are identified as LLMs [6] [15].Source: §2 · p. 3

Efficient LLM Inference

  • Prior LLM inference work covers kernel fusion, multi-GPU parallelism [30], quantization [8] [11] [35], and batching [3] [29]; this method groups sentences by predicted output length.The passage distinguishes few-shot query batching [3] and input-length grouping; generation costs exceed prompt forward costs.Source: §2 · p. 3

Response Length Prediction

  • Prior response-length prediction targets NAR translation, using dataset statistics, token-level prediction [13], [LENGTH] tokens [9] [12], or pooled encoder outputs with MLPs [20] [21] [24]; this method addresses varied LLM queries.The passage says NAR translation response lengths are closer to source lengths, unlike the diverse queries and response lengths in LLM inference.Source: §2 · p. 3

3 Response Length Perception

The section shows that instruction-tuned LLMs can estimate response length, then develops instruction tuning to improve prediction while separating it from response generation.

3.1 Perception in Advance (PiA)

  • With PiA instructions, GPT-4, ChatGPT, and Vicuna followed the length-estimation instruction for all 175 Alpaca seed queries, and word-based estimates were more reliable than token-based ones.The authors report that words better match how humans comprehend and generate responses.Source: §3.1 · p. 4
  • GPT-4 and Claude achieved Error(w) below 50 words and Acc-100 above 90%, while models with more parameters performed better at response-length prediction.Acc-50 and Acc-100 count predictions within 50 and 100 words of the actual word count, respectively.Source: §3.1 · p. 4
  • PiA can constrain generation to the estimated length: GPT-4 and Claude tend to tailor responses to it, while Vicuna 7B and 13B mostly ignore it.The authors also report that PiA may reduce response quality for smaller models; Vicuna-7B sometimes failed to generate a response after predicting length, attributed to limited capacity for handling multiple tasks.Source: §3.1 · pp. 4–5

3.2 Instruction Tuning

  • Instruction tuning reduced prediction error from 193 to 63 and improved Acc-50 by 18%, outperforming length-token fine-tuning and pooled-state MLP methods.For Vicuna, pooling plus an MLP failed completely when using LLaMA-7B or GPT-2 for length prediction, while length-token fine-tuning also fell short of Vicuna’s self-prediction.Source: Table 3 · p. 5, §3.2 · pp. 5–6

3.1 Perception in Advance (PiA)

  • Perception Only (PO) decouples length prediction from generation but is harder than PiA, with higher errors and lower accuracy.Because response lengths vary across samples, the authors target the maximum potential length rather than a mean; they note there is no definitive ground-truth length.Source: §3.1 · p. 5

3.2 Instruction Tuning

  • Instruction tuning used 10,000 Alpaca prompts, maximum response length across four generations as the target, number-only outputs, and LoRA training for three epochs.The approach aims to separate prediction from generation and enable smaller models to predict response lengths accurately.Source: §3.2 · p. 5

4 Sequence Scheduling

The section presents length-aware sequence scheduling to reduce redundant inference work and evaluates its throughput, component contributions, and behavior across group sizes.

4.1 Method

  • Grouping instructions with similar predicted response lengths reduces redundant computation, while batches that wait for every response can lose throughput when long responses delay short ones.With all samples generating to completion, throughput initially rises with batch size but begins to decline as larger batches are more likely to include long responses.Source: §4.1 · p. 6
  • Failure Collection and Recomputation caps generation at the batch’s maximum predicted length, then separately recomputes overlength failures after group processing.This limits disruption from inaccurate predictions while allowing shorter responses to finish sooner; the predictor’s reported acc-100 accuracy is 81%.Source: §4.1 · pp. 6–7
  • Variable Batch Size assigns larger batches to shorter responses, scaling batch size to maintain approximately the same number of tokens while managing memory use.For baseline batch size B0 at length L0, the adjusted size for length L is B0·L/L0.Source: §4.1 · p. 7
  • The predictor bins lengths in 50-token cells, rounding upward, and predicts the maximum length over four generation processes to buffer estimation errors and reduce failures.The passage contrasts this with predicting mean length, which can underestimate some queries and increase failure re-collection.Source: §4.1 · p. 7
  • Length prediction adds instruction processing and a few generated tokens, but its overhead can be offset by sequence-scheduling acceleration.The passage reports instruction processing takes the time of 1–4 generated tokens, while prediction typically generates 2–3 tokens.Source: §4.1 · p. 7, Figure 4 · p. 7

4.2 Experiments

  • Instruction-tuned length prediction yields an 85% throughput improvement, with throughput variance of 0.05 across three experiments.The instruction-tuned predictor performs best among those considered; the reported variance indicates stable throughput.Source: Table 4 · p. 8, §4.2 · p. 8
  • Predicting mean rather than maximum length raises the failure re-collection ratio to 29.8% from 15.3% and reduces throughput improvement to 45%.Using ground-truth maximum lengths gives an upper bound, and the proposed approach is only 0.25 samples/s slower.Source: §4.2 · p. 8
  • Binning strengthens VBS and each component contributes to throughput; Instruction-in-Wild results support effectiveness across datasets, while larger groups improve throughput with diminishing returns.The group-size analysis also notes a need to balance information-gathering overhead against the gains from larger groups.Source: §4.2 · pp. 8–9, Table 5 · p. 8, Table 6 · p. 9

5 Limitation and Discussion

The discussion identifies limits in response-length prediction, residual computation redundancy, and handling long input instructions. It also describes multi-GPU extensibility and suggests that LLMs’ understanding of their responses could enable faster inference methods.

Limitations and discussion

  • Accurate response-length prediction is not guaranteed, even with the instruction-tuned predictor, and its estimation accuracy still has room to improve.The authors describe their experimental results as promising while noting this limitation.Source: §5 · p. 9
  • Even with a ground-truth response length predictor, redundancy falls from 66% to 33% but is not eliminated; ORCA offers an alternative mitigation.The authors note that sequence scheduling reduces redundant computation but leaves room for further improvement.Source: §5 · p. 9
  • The method focuses less on input instructions, so very long instructions may cause redundant computation; combining it with input batch scheduling is proposed for future work.The authors connect this concern to increasing maximum token lengths supported by LLMs.Source: §5 · p. 9
  • The approach assumes the query group exceeds one GPU’s capacity; rising query volumes and support for longer sequences amplify varying-response-length challenges.The discussion cites GPT-4’s 32k and Claude’s 100K sequence-length support as examples.Source: §5 · p. 9
  • The approach extends to multi-GPU settings by reallocating sequence batches with different perceived response lengths across GPU nodes, maintaining efficiency and supporting larger models.The authors describe this as a scalable extension for high-performance computing environments.Source: §5 · p. 9
  • The authors infer that LLMs comprehensively understand their generated responses, suggesting this may enable faster inference, including non-autoregressive methods.Such methods could overcome performance constraints associated with sequential token generation.Source: §5 · p. 9

6 Conclusion

The paper combines advance response-length prediction with sequence scheduling to reduce computational waste in LLM inference. On real-world instruction datasets, the approach improved throughput while preserving performance quality.

6 Conclusion

  • 86% higher inference throughput without sacrificing performance quality was demonstrated on real-world instruction datasets using Vicuna-7B.The conclusion presents this as the experimental result for the proposed approach.Source: §6 · p. 9
  • Sequence scheduling groups queries with similar predicted response lengths into batches, while failure re-collection and variable batch size further enhance efficiency.The scheduling approach is motivated by reducing computational waste and improving inference throughput.Source: §6 · p. 9
  • Current LLMs perform well at perceiving response length before autoregressive decoding with the proposed Perception in Advance approach.Source: §6 · p. 9

Appendix · A Additional Instruction Tuning Implementation Details

The length predictor was instruction-tuned using sampled response lengths as targets and a length-only prompt, with Vicuna-style hyperparameters and LoRA on selected layers.

A Additional Instruction Tuning Implementation Details

B Distribution of Instruction-in-Wild Dataset

Instruction-in-the-Wild has a diverse response-length distribution with more long responses.

C Discussion on Sequence Scheduling with PiA

The discussion considers PiA-based sequence scheduling and KV-cache reuse, but retains recomputation because explored cache optimizations have practical costs and need further refinement.

C Discussion on Sequence Scheduling with PiA

  • GPT-4 and Claude can use PiA for sequence scheduling without additional weights, unlike the instruction-tuned approach using LoRA weights in the main text.Source: C Discussion on Sequence Scheduling… · p. 12
  • Reusing input-query KV cache could avoid recomputation during inference, but CPU–GPU offloading can outweigh the time saved; asynchronous partial offloading remains future work.Source: C Discussion on Sequence Scheduling… · p. 12
  • FlexGen quantization [29] minimally affected performance, but its added GPU-memory use can shrink batch size and degrade overall performance.Combining compression with offloading is proposed as a way to balance memory use and performance.Source: C Discussion on Sequence Scheduling… · p. 13
  • For PiA response-length perception, the pipeline retains recomputation because cache optimizations need further refinement to yield substantial practical gains.The paper leaves offloading and compression optimizations for future investigation.Source: C Discussion on Sequence Scheduling… · p. 13

D Inference Time Grows with Token Position Index

Transformer inference time increases linearly with token position because later tokens require self-attention over more keys and values. This makes saving redundant computation on longer sequences more impactful, so throughput growth can exceed the ratio of redundant tokens saved.

D Inference Time Grows with Token Position Index

Loading 2305.13144v2…