Beyond Prediction: Tail-Aware Scheduling for LLM Inference

• URL: http://arxiv.org/abs/2606.18431v1
• Date: Tue, 16 Jun 2026 19:25:37 GMT
• Title: Beyond Prediction: Tail-Aware Scheduling for LLM Inference
• Abstract summary: LLM serving exhibits extreme length variability, making size-based scheduling difficult in practice.<n>Recent schedulers approximate SJF/SRPT using predicted decode lengths or ranks.<n>We show that these prediction-driven policies can be fragile under distribution shifts, bursty arrivals, and GPU memory pressure.
• Score: 15.499732774491683
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: LLM serving exhibits extreme length variability, making size-based scheduling difficult in practice. Recent LLM schedulers approximate SJF/SRPT using predicted decode lengths or ranks and primarily report mean-centric metrics such as TTFT and TBT. We show that these prediction-driven policies can be fragile under distribution shifts, bursty arrivals, and GPU memory pressure, while offering limited control over the tail latency (P90-P99) that dominates user experience, even with perfect decode-length knowledge. We introduce a distribution-aware, prediction-free scheduling framework that replaces explicit length prediction with soft priority boosting driven by lightweight statistical signals. Our design co-optimizes scheduling and cache-aware preemption to account for memory-coupled decode dynamics across workload mixes. Evaluated on production and open-source traces, our method reduces P99 TTLT by up to 35-50% relative to SRPT with perfect length knowledge and reduces TTFT by 34-47% across workloads, including reasoning-heavy and chat-heavy tasks. These results demonstrate a robust alternative for optimizing tail latency in online LLM serving.

Related papers

• Predicting LLM Output Length via Entropy-Guided Representations [13.351384070796747]
  We introduce a lightweight framework that reuses the main model's internal hidden states for efficient length prediction.<n>Our framework features two core components: 1) Entropy-Guided Token Pooling (EGTP), which uses on-the-fly activations and token entropy for highly accurate static prediction.
  arXiv  Detail & Related papers  (2026-02-12T10:49:04Z)
• Intra-request branch orchestration for efficient LLM reasoning [52.68946975865865]
  Large Language Models (LLMs) increasingly rely on inference-time reasoning algorithms to improve accuracy on complex tasks.<n>Prior work has largely focused on reducing token usage, often at the expense of accuracy, while overlooking other latency factors.<n>We present DUCHESS, an LLM serving system that reduces cost and latency without sacrificing accuracy through intra-request branch orchestration guided by predictions.
  arXiv  Detail & Related papers  (2025-09-29T15:52:08Z)
• Block: Balancing Load in LLM Serving with Context, Knowledge and Predictive Scheduling [0.0]
  Block is a distributed scheduling framework designed to optimize load balancing and auto-provisioning across instances in serving frameworks.<n>It operates as a fully distributed, stateless, and predictive scheduling system to achieve low overhead, reliability, and scalability.
  arXiv  Detail & Related papers  (2025-08-05T16:27:10Z)
• Optimal Scheduling Algorithms for LLM Inference: Theory and Practice [6.043830060363904]
  This paper develops a theoretical framework that models routing and scheduling in Large Language Model inference systems.<n>We identify two key design principles-optimal tiling and dynamic resource allocation-that are essential for achieving high throughput.<n>We show that the Resource-Aware Dynamic (RAD) scheduler achieves throughput optimality under mild conditions.
  arXiv  Detail & Related papers  (2025-08-01T18:12:21Z)
• How to Train Your LLM Web Agent: A Statistical Diagnosis [96.86317871461834]
  We present the first statistically grounded study on compute allocation for LLM web-agent post-training.<n>Our approach uses a two-stage pipeline, training a Llama 3.1 8B student to imitate a Llama 3.3 70B teacher via supervised fine-tuning (SFT) and on-policy reinforcement learning.<n>Our results show that combining SFT with on-policy RL consistently outperforms either approach alone on both WorkArena and MiniWob++.
  arXiv  Detail & Related papers  (2025-07-05T17:12:33Z)
• $\texttt{SPECS}$: Faster Test-Time Scaling through Speculative Drafts [55.231201692232894]
  $textttSPECS$ is a latency-aware test-time scaling method inspired by speculative decoding.<n>Our results show that $textttSPECS$matches or surpasses beam search accuracy while reducing latency by up to $sim$19.1%.
  arXiv  Detail & Related papers  (2025-06-15T05:50:05Z)
• Semi-Clairvoyant Scheduling of Speculative Decoding Requests to Minimize LLM Inference Latency [4.372762934308627]
  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.
  arXiv  Detail & Related papers  (2025-05-20T04:12:37Z)
• Length Controlled Generation for Black-box LLMs [70.57649832433451]
  Large language models (LLMs) have demonstrated impressive instruction following capabilities, but struggle to accurately manage the length of generated text.<n>We propose a novel iterative sampling framework for text length control, integrating the Metropolis-Hastings algorithm with an importance sampling acceleration strategy.<n>Our framework achieves almost 100% success rates of length control on Llama3.1 for tasks such as length-controlled abstractive summarization.
  arXiv  Detail & Related papers  (2024-12-19T09:07:38Z)
• 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)
• Sparse Fine-tuning for Inference Acceleration of Large Language Models [48.285897264669984]
  We consider the problem of accurate sparse fine-tuning of large language models (LLMs) We perform a detailed study of distillation-type losses, determining an L2-based distillation approach we term SquareHead. For MPT text generation, we show for the first time that sparse fine-tuning can reach 75% sparsity without accuracy drops.
  arXiv  Detail & Related papers  (2023-10-10T18:28:38Z)
• LoRAPrune: Structured Pruning Meets Low-Rank Parameter-Efficient Fine-Tuning [56.88751562302793]
  Low-rank adaption (LoRA) has emerged to fine-tune large language models (LLMs) LoRAPrune is a new framework that delivers an accurate structured pruned model in a highly memory-efficient manner. LoRAPrune achieves a reduction in perplexity by 4.81 on WikiText2 and 3.46 on PTB, while also decreasing memory usage by 52.6%.
  arXiv  Detail & Related papers  (2023-05-28T15:15:48Z)
• Decoder Tuning: Efficient Language Understanding as Decoding [84.68266271483022]
  We present Decoder Tuning (DecT), which in contrast optimize task-specific decoder networks on the output side. By gradient-based optimization, DecT can be trained within several seconds and requires only one P query per sample. We conduct extensive natural language understanding experiments and show that DecT significantly outperforms state-of-the-art algorithms with a $200times$ speed-up.
  arXiv  Detail & Related papers  (2022-12-16T11:15:39Z)

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.