Research map / Large language models / Reasoning and chain of thought

Beyond Prediction: Tail-Aware Scheduling for LLM Inference

ICML 2026 · Large language models › Reasoning and chain of thought · approach: Efficient LLM serving · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Theoretical note bounding the starvation penalty (crossing work) of an age-based boost scheduling rule (UniBoost-style) relative to a known-size benchmark, showing it differs by only a factor e^rho.

Problem

Whether age-based (attained-service) boost scheduling approximating SJF/SRPT for LLM inference causes severe starvation of large jobs, measured via crossing work tail behavior.

Approach

Introduces an age-based boost transform b_gamma(x) = (1/gamma) log(e^{gamma x}/(e^{gamma x}-1)) and shows its crossing-work functional equals the known-size one times e^rho, plus a lemma that E[e^{gamma V}] is finite for attained-service boosts with polynomially bounded decay.

Key results

• Theorem: crossing work under age-based profile equals known-size crossing work times e^rho, so the gap is uniformly bounded by e under rho<1.
• Lemma: for attained-service boosts with b(a) <= O(a^{-1/(1+eps)}) decreasing, E[e^{gamma V}] is finite; applies to UniBoost since its boost is O(log(1/a)).

Limitations

• Purely theoretical; the note explicitly states the theorem is not a full response-time theorem and relies on mild assumptions (FCFS dominant, crossing work decays faster).
• The lemma's proof is a sketch and the bound uses a loosely stated O(1/sqrt) condition; no LLM serving experiments are included in this excerpt.
• Heuristic response-time decomposition is not rigorous.

Experimental setup

Baselines: FCFS known-size SJF/SRPT benchmark

Builds on: Yu and Scully (2024) boost analysis LAS scheduling UniBoost

Closest papers by meaning

• Geometry-Aware Online Scheduling for LLM Serving: From Theoretical Bound to System Practice (NeurIPS 2026 · similarity 0.92)
• Efficient LLM Scheduling by Learning to Rank (NeurIPS 2024 · similarity 0.90)
• MAPS: Memory-Aware Predictive Scheduling Framework for Large Language Model Serving (ICML 2026 · similarity 0.90)
• Predicting LLM Output Length via Entropy-Guided Representations (ICLR 2026 · similarity 0.88)
• A Queueing-Theoretic Framework for Stability Analysis of LLM Inference with KV Cache Memory Constraints (ICML 2026 · similarity 0.88)
• Yggdrasil: Bridging Dynamic Speculation and Static Runtime for Latency-Optimal Tree-Based LLM Decoding (NeurIPS 2025 · similarity 0.88)