Semi-Clairvoyant Scheduling of Speculative Decoding Requests to Minimize LLM Inference Latency

• URL: http://arxiv.org/abs/2505.17074v1
• Date: Tue, 20 May 2025 04:12:37 GMT
• Title: Semi-Clairvoyant Scheduling of Speculative Decoding Requests to Minimize LLM Inference Latency
• Authors: Ruixiao Li, Fahao Chen, Peng Li,
• Abstract summary: We propose a semi-clairvoyant request scheduling algorithm called Least-Attained/Perceived-Service for Speculative Decoding (LAPS-SD)<n>LAPS-SD can effectively minimize average inference latency by adaptively scheduling requests according to their features during decoding.<n>Experiments show that LAPS-SD reduces inference latency by approximately 39% compared to state-of-the-art scheduling methods.
• Score: 4.372762934308627
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Speculative decoding accelerates Large Language Model (LLM) inference by employing a small speculative model (SSM) to generate multiple candidate tokens and verify them using the LLM in parallel. This technique has been widely integrated into LLM inference serving systems. However, inference requests typically exhibit uncertain execution time, which poses a significant challenge of efficiently scheduling requests in these systems. Existing work estimates execution time based solely on predicted output length, which could be inaccurate because execution time depends on both output length and token acceptance rate of verification by the LLM. In this paper, we propose a semi-clairvoyant request scheduling algorithm called Least-Attained/Perceived-Service for Speculative Decoding (LAPS-SD). Given a number of inference requests, LAPS-SD can effectively minimize average inference latency by adaptively scheduling requests according to their features during decoding. When the token acceptance rate is dynamic and execution time is difficult to estimate, LAPS-SD maintains multiple priority queues and allows request execution preemption across different queues. Once the token acceptance rate becomes stable, LAPS-SD can accurately estimate the execution time and schedule requests accordingly. Extensive experiments show that LAPS-SD reduces inference latency by approximately 39\% compared to state-of-the-art scheduling methods.

Related papers

• Can Prompt Difficulty be Online Predicted for Accelerating RL Finetuning of Reasoning Models? [62.579951798437115]
  This work investigates iterative approximate evaluation for arbitrary prompts.<n>It introduces Model Predictive Prompt Selection (MoPPS), a Bayesian risk-predictive framework.<n>MoPPS reliably predicts prompt difficulty and accelerates training with significantly reduced rollouts.
  arXiv  Detail & Related papers  (2025-07-07T03:20:52Z)
• Semantic Scheduling for LLM Inference [48.19648297172146]
  We introduce the concept of semantic scheduling in scheduling of requests from large language models (LLM)<n>We present a novel scheduling algorithm with optimal time complexity, designed to minimize the overall waiting time in LLM-based prompt scheduling.
  arXiv  Detail & Related papers  (2025-06-13T20:15:58Z)
• Task-Oriented Feature Compression for Multimodal Understanding via Device-Edge Co-Inference [49.77734021302196]
  We propose a task-oriented feature compression (TOFC) method for multimodal understanding in a device-edge co-inference framework.<n>To enhance compression efficiency, multiple entropy models are adaptively selected based on the characteristics of the visual features.<n>Results show that TOFC achieves up to 60% reduction in data transmission overhead and 50% reduction in system latency.
  arXiv  Detail & Related papers  (2025-03-17T08:37:22Z)
• Speeding up Speculative Decoding via Approximate Verification [7.754712828900729]
  Speculative Decoding (SD) is a recently proposed technique for faster inference using Large Language Models (LLMs)<n>We propose SPRINTER, which utilizes a low-complexity verifier trained to predict if tokens generated from a draft LLM would be accepted by the target LLM.<n>We present a theoretical analysis of SPRINTER, examining the statistical properties of the generated tokens, as well as the expected reduction in latency.
  arXiv  Detail & Related papers  (2025-02-06T23:10:53Z)
• Multi-Bin Batching for Increasing LLM Inference Throughput [19.652542432683234]
  Large language models (LL) grow in popularity improving the efficiency of their systems.<n> requests is a critical step in scheduling jobs on servers.<n> requests often have varying generation lengths, causing resource underutilization.<n>We formalize this problem from a queueing-theoretic perspective, and aim to design a throughput control policy.
  arXiv  Detail & Related papers  (2024-12-03T03:16:12Z)
• 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.<n>Applying Speculative Decoding (SD) to generative recommendation presents unique challenges due to the requirement of generating top-K items.<n>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)
• Don't Stop Me Now: Embedding Based Scheduling for LLMs [22.099820814682513]
  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.
  arXiv  Detail & Related papers  (2024-10-01T19:51:07Z)
• Efficiency Unleashed: Inference Acceleration for LLM-based Recommender Systems with Speculative Decoding [61.45448947483328]
  We introduce Lossless Acceleration via Speculative Decoding for LLM-based Recommender Systems (LASER)<n>LASER features a Customized Retrieval Pool to enhance retrieval efficiency and Relaxed Verification to improve the acceptance rate of draft tokens.<n>LASER achieves a 3-5x speedup on public datasets and saves about 67% of computational resources during the online A/B test.
  arXiv  Detail & Related papers  (2024-08-11T02:31:13Z)
• InfLLM: Training-Free Long-Context Extrapolation for LLMs with an Efficient Context Memory [93.20588235940453]
  In this paper, we introduce a training-free memory-based method, InfLLM. InfLLM stores distant contexts into additional memory units and employs an efficient mechanism to lookup token-relevant units for attention. Even when the sequence length is scaled to $1,024$K, InfLLM still effectively captures long-distance dependencies.
  arXiv  Detail & Related papers  (2024-02-07T06:50:42Z)
• Fast Distributed Inference Serving for Large Language Models [12.703624317418237]
  We present FastServe, a distributed inference serving system for large language models (LLMs) FastServe exploits the autoregressive pattern of LLM inference to enable preemption at the granularity of each output token. We build a system prototype of FastServe and experimental results show that compared to the state-of-the-art solution vLLM, FastServe improves the throughput by up to 31.4x and 17.9x under the same average and tail latency requirements, respectively.
  arXiv  Detail & Related papers  (2023-05-10T06:17:50Z)

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.