Formal schedulability analysis for LLM inference: TTFT and TBT deadline guarantees via response-time theory

Résumé

Introduction Large language model (LLM) inference systems operate under strict latency service-level objectives (SLOs): a deadline on the first output token (TTFT) and a maximum inter-token interval (TBT). Real-time (RT) scheduling theory provides formal schedulability tests, worst-case response-time (WCRT) bounds, and admission control, yet existing LLM schedulers ignore these tools entirely. Methods We present Chronos , the first schedulability framework for LLM inference grounded in RT theory. A two-phase task model maps each request to a sporadic prefill job with a TTFT deadline and a decode task whose iterations are bounded by the TBT SLO. From this model we derive a closed-form WCRT bound for TTFT, a TBT capacity condition, a prefill–decode interference analysis, and a sound admission control algorithm proved correct analytically. We validate Chronos with a discrete-event simulator parameterised by roofline-model estimates for a 7B-parameter model on an A100 GPU. Each experiment replays 50,000 requests sub-sampled from a one-week, 44-million-request Azure LLM Inference production trace. Results At 10× nominal load, where admission-uncontrolled schedulers reach 99.4% TTFT miss rates, Chronos maintains zero misses while admitting 53.9% of arrivals. At 5× load it admits 88.9% of requests with P99 TTFT of 161 ms—more than 2× below uncontrolled baselines. No admitted request ever misses its TTFT or TBT deadline. Discussion These results demonstrate that classical RT scheduling constructs translate directly and effectively to LLM inference, providing formal, verifiable latency guarantees that heuristic schedulers cannot offer.

Citer ce document

Accès au document

Texte intégral en lecture en ligne, réservé aux abonnés SPHAERO et aux membres de l'institution. Se connecter

Auteur(s)

Statistiques

Consultations : 1

Téléchargements : 0