Scheduling LLM Inference with Uncertainty-Aware Output Length Predictions

• URL: http://arxiv.org/abs/2604.00499v1
• Date: Wed, 01 Apr 2026 05:31:21 GMT
• Title: Scheduling LLM Inference with Uncertainty-Aware Output Length Predictions
• Abstract summary: Existing methods usually predict a single output length for each request to facilitate scheduling.<n>We propose Tail Inflated Expectation (TIE) to replace the output length in SJF scheduling.<n>TIE reduces the per-token latency by $2.31times$ for online inference and improves throughput by $1.42times for offline data generation.
• Score: 16.877407702260243
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: To schedule LLM inference, the \textit{shortest job first} (SJF) principle is favorable by prioritizing requests with short output lengths to avoid head-of-line (HOL) blocking. Existing methods usually predict a single output length for each request to facilitate scheduling. We argue that such a \textit{point estimate} does not match the \textit{stochastic} decoding process of LLM inference, where output length is \textit{uncertain} by nature and determined by when the end-of-sequence (EOS) token is sampled. Hence, the output length of each request should be fitted with a distribution rather than a single value. With an in-depth analysis of empirical data and the stochastic decoding process, we observe that output length follows a heavy-tailed distribution and can be fitted with the log-t distribution. On this basis, we propose a simple metric called Tail Inflated Expectation (TIE) to replace the output length in SJF scheduling, which adjusts the expectation of a log-t distribution with its tail probabilities to account for the risk that a request generates long outputs. To evaluate our TIE scheduler, we compare it with three strong baselines, and the results show that TIE reduces the per-token latency by $2.31\times$ for online inference and improves throughput by $1.42\times$ for offline data generation.

Related papers

• OUTLETS: Output-Length Prediction from Speculative Decoding Backbones [9.273938403693576]
  Heavy-tailed distribution of output lengths in Large Language Model (LLM) serving poses major challenges for resource provisioning and cluster scheduling.<n>We identify a structural connection between speculative decoding (SD) and length prediction.<n>We introduce OUTLETS, which repurposes the speculative backbone as a trajectory-aware length predictor.
  arXiv  Detail & Related papers  (2026-09-01T11:00:39Z)
• Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata [57.27430779838529]
  We present an exact and tractable algorithm for sampling from the constrained mean-field posterior under any constraint expressible as a finite automaton.<n>The approach guarantees constraint satisfaction by construction, supports both greedy and sampling-based decoding, and is compatible with parallel and block-wise decoding.<n> Empirical evaluations on Dream-7B and LLaDA-8 show substantial accuracy gains across various tasks.
  arXiv  Detail & Related papers  (2026-07-08T05:48:57Z)
• Robust Length Prediction: A Perspective from Heavy-Tailed Prompt-Conditioned Distributions [61.56973419225008]
  Existing methods for output-length prediction are unreliable for prompt-only predictions.<n>We propose prompt-conditioned length distribution methods, which construct training targets from the same prompt.<n>Experiments across diverse scenarios show consistent gains in prediction quality.
  arXiv  Detail & Related papers  (2026-04-09T07:49:52Z)
• 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)
• Catch Your Breath: Adaptive Computation for Self-Paced Sequence Production [55.76222360698305]
  We explore a class of supervised training objectives that allow a language model to dynamically and autonomously scale the number of compute steps used for each input token.<n>For any token, the model can request additional compute steps by emitting a don't know> output.<n>We find that the CYB model requests additional steps when doing so improves accuracy, and the model adapts its processing time to token-level complexity and context.
  arXiv  Detail & Related papers  (2025-10-13T21:07:05Z)
• Rethinking Thinking Tokens: LLMs as Improvement Operators [80.12087211785949]
  Reasoning training incentivizes LLMs to produce long chains of thought (long CoT), which allows them to explore solution strategies with self-checking.<n>This results in higher accuracy, but inflates context length, token/compute cost, and answer latency.<n>We ask: Can current models leverage their metacognition to provide other combinations on this Pareto frontier?<n>We identify an interesting inference family Parallel-Distill-Refine (PDR), which performs the following: (i) generate diverse drafts in parallel; (ii) distill them into a bounded, textual workspace; and (iii) refine conditioned on this workspace
  arXiv  Detail & Related papers  (2025-10-01T17:08:59Z)
• Adaptively Robust LLM Inference Optimization under Prediction Uncertainty [9.541681114575812]
  We study the problem of optimizing Large Language Model (LLM) inference scheduling to minimize total latency.<n>A key challenge in LLM inference scheduling is that while the prompt length is known upon arrival, the output length, which critically impacts memory usage and processing time, is unknown.<n>We propose algorithms that leverage machine learning to predict output lengths, assuming the prediction provides an interval classification (min-max range) for each request.
  arXiv  Detail & Related papers  (2025-08-20T08:55:26Z)
• 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)
• Fractured Chain-of-Thought Reasoning [61.647243580650446]
  We introduce Fractured Sampling, a unified inference-time strategy that interpolates between full CoT and solution-only sampling.<n>We show that Fractured Sampling consistently achieves superior accuracy-cost trade-offs, yielding steep log-linear scaling gains in Pass@k versus token budget.
  arXiv  Detail & Related papers  (2025-05-19T11:30:41Z)
• Beyond Next Token Probabilities: Learnable, Fast Detection of Hallucinations and Data Contamination on LLM Output Distributions [60.43398881149664]
  We introduce LOS-Net, a lightweight attention-based architecture trained on an efficient encoding of the LLM Output Signature.<n>It achieves superior performance across diverse benchmarks and LLMs, while maintaining extremely low detection latency.
  arXiv  Detail & Related papers  (2025-03-18T09:04:37Z)
• PecSched: Preemptive and Efficient Cluster Scheduling for LLM Inference [11.194752361478567]
  Existing cluster-level LLM scheduling strategies primarily target short-input requests with lengths below 2K.<n>We propose PecSched, a preemptive and efficient cluster-level LLM inference scheduler.<n>We show that PecSched reduces the 99th percentile queueing delay of short-input requests by up to 92% and improves their throughput by up to 595%.
  arXiv  Detail & Related papers  (2024-09-23T15:16:29Z)
• 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)
• CALF: Aligning LLMs for Time Series Forecasting via Cross-modal Fine-Tuning [59.88924847995279]
  We propose a novel Cross-Modal LLM Fine-Tuning (CALF) framework for MTSF.<n>To reduce the distribution discrepancy, we develop the cross-modal match module.<n>CALF establishes state-of-the-art performance for both long-term and short-term forecasting tasks.
  arXiv  Detail & Related papers  (2024-03-12T04:04:38Z)

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.