Pith. sign in

REVIEW 9 cited by

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

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2410.01035 v1 pith:N64Y3K2S submitted 2024-10-01 cs.LG

Rana Shahout , Eran Malach , Chunwei Liu , Weifan Jiang , Minlan Yu , Michael Mitzenmacher This is my paper
classification cs.LG
keywords preemptionrequestschedulingsystemscompletionmemoryoutputsrpt
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original 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.

Discussion (0). Sign in to comment.

Forward citations

Cited by 9 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Efficiency and Cost Alignment in Batched LLM Serving via Resource-Fair Scheduling

    cs.DC 2026-08 conditional novelty 7.0 of 10

    A resource-fair batching policy (ISJL) that keeps co-batched LLM requests within a token-progress window is proved 3/4-competitive in an offline model and empirically outperforms FCFS, SJF, and LJF on throughput and latency.

  2. Geometry-Aware Online Scheduling for LLM Serving: From Theoretical Bound to System Practice

    cs.AI 2026-06 unverdicted novelty 7.0 of 10

    SVF scheduling algorithm achieves a competitive ratio of 3 for LLM serving and integrates into vLLM to reduce average and tail latency.

  3. Beyond Prediction: Tail-Aware Scheduling for LLM Inference

    cs.LG 2026-06 unverdicted novelty 7.0 of 10

    Presents a distribution-aware scheduling framework for LLM inference that reduces P99 TTLT by 35-50% and TTFT by 34-47% versus SRPT with perfect length knowledge using statistical signals instead of predictions.

  4. Online Linear Programming for Multi-Objective Routing in LLM Serving

    cs.AI 2026-07 conditional novelty 6.0 of 10

    Online LP bid-price routing with warm-started dual gradient updates substantially improves multi-SLO LLM decode routing over heuristics in simulation.

  5. PALS: Power-Aware LLM Serving for Mixture-of-Experts Models

    cs.AI 2026-05 unverdicted novelty 6.0 of 10

    PALS adds dynamic GPU power capping to LLM serving frameworks like vLLM, jointly tuning it with batch size via offline models and feedback control to improve energy efficiency up to 26.3% and cut QoS violations 4-7x o...

  6. Tackling the Data-Parallel Load Balancing Bottleneck in LLM Serving: Practical Online Routing at Scale

    cs.DC 2026-05 unverdicted novelty 6.0 of 10

    BalanceRoute uses a piecewise-linear F-score (with optional short lookahead) for sticky request routing in LLM serving, reducing DP imbalance and raising end-to-end throughput versus vLLM baselines on production and A...

  7. Tackling the Data-Parallel Load Balancing Bottleneck in LLM Serving: Practical Online Routing at Scale

    cs.DC 2026-05 unverdicted novelty 6.0 of 10

    BalanceRoute reduces data-parallel imbalance in LLM inference via F-score routing and lookahead, yielding higher end-to-end throughput on 144-NPU clusters versus vLLM baselines.

  8. A Queueing-Theoretic Framework for Stability Analysis of LLM Inference with KV Cache Memory Constraints

    cs.LG 2026-05 unverdicted novelty 6.0 of 10

    A queueing model derives stability conditions for LLM inference services under combined compute and KV cache memory limits, with experimental validation showing typical deviations under 10%.

  9. Position: LLM Serving Needs Mathematical Optimization and Algorithmic Foundations, Not Just Heuristics

    cs.DC 2026-05 accept novelty 4.0 of 10

    LLM serving requires mathematical optimization and algorithms with provable guarantees rather than generic heuristics that fail unpredictably on LLM workloads.

Pith tools