Large language model (LLM)-powered agentic AI services increasingly require ultra‑low inference latency, prompting the deployment of LLMs on distributed edge servers. Edge nodes differ in bandwidth and compute power, and each request’s inference state evolves over time, making server selection for incoming requests time‑varying and tightly coupled across slots. This work proposes an online scheduling framework that minimizes long‑term average end‑to‑end latency while balancing workload across heterogeneous edge servers.
Key Challenges:
- Conventional latency models only capture coarse‑grained, single‑stage inference and cannot represent the multi‑stage pipeline—transmission, prefill, iterative decoding—and the evolution of the KV cache.
- The latency impact of a scheduling decision is observable only after request completion, hindering immediate evaluation.
Technical Approach:
- Cross‑slot inference model: Decomposes each request into four sub‑processes—network transmission, prefill, step‑wise decoding, and KV‑cache growth. Server load is quantified by a memory‑time consumption metric of the KV cache.
- LYREO algorithm:
- Transforms the long‑term load‑balancing constraint into a Lyapunov optimization problem, yielding an online virtual‑queue update rule.
- Employs reward redistribution together with sequence‑based return prediction to convert delayed latency penalties into timely learning signals for earlier decisions.
Experimental Findings: Across diverse bandwidth and compute configurations, LYREO consistently outperforms learning‑based and heuristic baselines, reducing average latency by ~15%‑30% and decreasing load variance by ~40%, confirming the effectiveness of the cross‑slot model and Lyapunov‑based constraint handling.
Review