Don't Stop Me Now: Embedding Based Scheduling for LLMs

• URL: http://arxiv.org/abs/2410.01035v1
• Date: Tue, 1 Oct 2024 19:51:07 GMT
• Title: Don't Stop Me Now: Embedding Based Scheduling for LLMs
• Authors: Rana Shahout, Eran Malach, Chunwei Liu, Weifan Jiang, Minlan Yu, Michael Mitzenmacher,
• Abstract summary: Size-based scheduling algorithms like Shortest Remaining Process Time (SRPT) aim to reduce average request completion time. We propose a prediction-based SRPT variant with limited preemption designed to account for memory overhead in LLM systems.
• Score: 22.099820814682513
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Efficient scheduling is crucial for interactive Large Language Model (LLM) applications, where low request completion time directly impacts user engagement. Size-based scheduling algorithms like Shortest Remaining Process Time (SRPT) aim to reduce average request completion time by leveraging known or estimated request sizes and allowing preemption by incoming jobs with shorter service times. However, two main challenges arise when applying size-based scheduling to LLM systems. First, accurately predicting output lengths from prompts is challenging and often resource-intensive, making it impractical for many systems. As a result, the state-of-the-art LLM systems default to first-come, first-served scheduling, which can lead to head-of-line blocking and reduced system efficiency. Second, preemption introduces extra memory overhead to LLM systems as they must maintain intermediate states for unfinished (preempted) requests. In this paper, we propose TRAIL, a method to obtain output predictions from the target LLM itself. After generating each output token, we recycle the embedding of its internal structure as input for a lightweight classifier that predicts the remaining length for each running request. Using these predictions, we propose a prediction-based SRPT variant with limited preemption designed to account for memory overhead in LLM systems. This variant allows preemption early in request execution when memory consumption is low but restricts preemption as requests approach completion to optimize resource utilization. On the theoretical side, we derive a closed-form formula for this SRPT variant in an M/G/1 queue model, which demonstrates its potential value. In our system, we implement this preemption policy alongside our embedding-based prediction method.

Related papers

• ALISE: Accelerating Large Language Model Serving with Speculative Scheduling [7.367068885621016]
  Large Language Models (LLMs) represent a revolutionary advancement in the contemporary landscape of artificial general intelligence (AGI) In this paper, we propose a new efficient LLM inference serving framework, named ALISE. We show that ALISE improves the throughput of inference serving by up to 1.8x and 2.1x under the same latency constraint on the Alpaca and ShareGPT datasets, respectively.
  arXiv  Detail & Related papers  (2024-10-31T00:58:11Z)
• Fast Inference for Augmented Large Language Models [14.195265302357148]
  Augmented Large Language Models (LLMs) enhance the capabilities of standalone LLMs by integrating external data sources through API calls. Traditional size-based scheduling algorithms, such as Shortest Job First (SJF), become less effective at minimizing completion times. We propose LAMPS, a novel LLM inference framework for augmented LLMs.
  arXiv  Detail & Related papers  (2024-10-23T19:53:30Z)
• Efficient Inference for Large Language Model-based Generative Recommendation [78.38878421030522]
  Large Language Model (LLM)-based generative recommendation has achieved notable success, yet its practical deployment is costly. Applying Speculative Decoding (SD) to generative recommendation presents unique challenges due to the requirement of generating top-K items. We propose an alignment framework named AtSpeed, which presents the AtSpeed-S optimization objective for top-K alignment under the strict top-K verification.
  arXiv  Detail & Related papers  (2024-10-07T16:23:36Z)
• Efficient LLM Scheduling by Learning to Rank [19.33941579312897]
  We show that it is possible to predict the relative ranks of output lengths in a batch of requests, using learning to rank. We develop a novel scheduler for LLM inference and serving that can approximate the shortest-job-first (SJF) schedule better than existing approaches.
  arXiv  Detail & Related papers  (2024-08-28T13:35:54Z)
• Turning Trash into Treasure: Accelerating Inference of Large Language Models with Token Recycling [53.58854856174773]
  Speculative decoding is an approach to accelerate inference through a guess-and-verify paradigm. Token Recycling stores candidate tokens in an adjacency matrix and employs a breadth-first search algorithm. It significantly outperforms existing train-free methods by 30% and even a training method by 25%.
  arXiv  Detail & Related papers  (2024-08-16T12:20:56Z)
• Efficient Prompting for LLM-based Generative Internet of Things [88.84327500311464]
  Large language models (LLMs) have demonstrated remarkable capacities on various tasks, and integrating the capacities of LLMs into the Internet of Things (IoT) applications has drawn much research attention recently. Due to security concerns, many institutions avoid accessing state-of-the-art commercial LLM services, requiring the deployment and utilization of open-source LLMs in a local network setting. We propose a LLM-based Generative IoT (GIoT) system deployed in the local network setting in this study.
  arXiv  Detail & Related papers  (2024-06-14T19:24:00Z)
• Preble: Efficient Distributed Prompt Scheduling for LLM Serving [8.706905652975554]
  This paper proposes Preble, the first distributed LLM serving platform that targets and optimize for prompt sharing. We designed a distributed scheduling system that co-optimizes KV state reuse and computation load-balancing with a new scheduling algorithm and a hierarchical scheduling mechanism. Our evaluation of Preble with real workloads and request arrival patterns on two open-source LLMs shows that Preble outperforms the SOTA serving systems by 1.5X to 14.5X on average latency and 2X to 10X on p99 latency.
  arXiv  Detail & Related papers  (2024-05-08T06:30:58Z)
• Efficient Interactive LLM Serving with Proxy Model-based Sequence Length Prediction [8.705908108054878]
  Large models (LLMs) have been driving a new wave of AI applications across numerous domains. We present a speculative shortest-job-first (SSJF) scheduler that uses a light proxy model to predict LLM output sequence lengths.
  arXiv  Detail & Related papers  (2024-04-12T14:46:15Z)
• RelayAttention for Efficient Large Language Model Serving with Long System Prompts [59.50256661158862]
  This paper aims to improve the efficiency of LLM services that involve long system prompts. handling these system prompts requires heavily redundant memory accesses in existing causal attention algorithms. We propose RelayAttention, an attention algorithm that allows reading hidden states from DRAM exactly once for a batch of input tokens.
  arXiv  Detail & Related papers  (2024-02-22T18:58:28Z)
• Tree-Planner: Efficient Close-loop Task Planning with Large Language Models [63.06270302774049]
  Tree-Planner reframes task planning with Large Language Models into three distinct phases. Tree-Planner achieves state-of-the-art performance while maintaining high efficiency.
  arXiv  Detail & Related papers  (2023-10-12T17:59:50Z)
• LaGR-SEQ: Language-Guided Reinforcement Learning with Sample-Efficient Querying [71.86163159193327]
  Large language models (LLMs) have recently demonstrated their impressive ability to provide context-aware responses via text. This ability could potentially be used to predict plausible solutions in sequential decision making tasks pertaining to pattern completion. We introduce LaGR, which uses this predictive ability of LLMs to propose solutions to tasks that have been partially completed by a primary reinforcement learning (RL) agent.
  arXiv  Detail & Related papers  (2023-08-21T02:07:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.