1
End-to-End Latency-Minimizing and Load-Balanced Request Scheduling for Edge LLM Inference in Agentic AI Services
arXiv:2609.17193v1 [cs.AI] 15 Sep 2026
Zhen Li, Jun Cai, Senior Member, IEEE, Haoran Gao, An Li, and Tan Li
Abstract—Large language model (LLM)-powered agentic AI services increasingly demand low-latency inference, motivating the deployment of LLMs across distributed edge servers. However, heterogeneous communication and computing capabilities, together with dynamically evolving inference states, make the edge server selection for each incoming request time-varying and tightly coupled across slots. In this paper, we investigate an online request scheduling framework for edge LLM inference that jointly minimizes long-term average end-to-end latency and regulates workload distribution across heterogeneous edge servers. Two main challenges arise in this context. First, conventional latency models cannot accurately capture the fine-grained dynamics of multi-stage LLM execution. Second, the latency consequence of a scheduling decision is observed only after request completion, making immediate decision evaluation difficult. To address these challenges, we develop a cross-slot inference model that captures transmission, prefill, iteration-level decoding, and key-value (KV) cache evolution for each diverse request, and characterize server workload through a KV cache memory-time consumption metric. We propose the LYREO approach that transforms the long-term load-balancing constraint via Lyapunov optimization and employs reward redistribution with sequencebased return prediction to convert delayed outcomes into timely learning signals for earlier decisions. Simulations under various configurations demonstrate that LYREO consistently achieves lower latency and more balanced load distribution than representative learning-based and heuristic baseline schemes. Index Terms—Agentic AI, LLM inference, request scheduling, load balancing, reward redistribution.
I. I NTRODUCTION GENTIC artificial intelligence (agentic AI) is emerging as a key paradigm for intelligent networks, where autonomous applications continuously perceive environments, reason, and act with limited human intervention [1]. As the core intelligence component of agentic AI systems, large language models (LLMs) provide the reasoning and planning capabilities required for goal-directed autonomy. Unlike conventional single-invocation applications, agentic AI repeatedly interacts with LLMs through observe-think-act cycles, so each invocation sits on the closed loop’s critical path. A delayed response directly postpones the next action, making inference latency a key determinant of system responsiveness [2]. Typically, LLM inference is hosted on remote cloud servers, but repeatedly forwarding inference requests to the cloud incurs substantial wide-area transmission delay, making agentic services vulnerable to network congestion and unstable connec-
A
Zhen Li, Jun Cai (corresponding author), An Li, and Haoran Gao are with the Department of Electrical and Computer Engineering, Concordia University, Montreal, QC, H3G 1M8, Canada. (E-mail: {zhen.li, jun.cai}@concordia.ca, {haoran.gao, an.li}@mail.concordia.ca). Tan Li is with the Department of Computer Science, Hang Seng University of Hong Kong, Hong Kong SAR. (E-mail: [email protected]).
tivity. Edge deployment of LLMs physically shortens transmission paths, mitigating cloud-side queuing and contention [3]. However, when multiple agentic AI applications share edgehosted LLMs, their requests inevitably overlap in time and vary widely in input/output lengths and latency expectations, competing for edge servers’ heterogeneous communication, computation, and memory resources. Since the end-to-end latency is shaped by fluctuating wireless conditions, disparate server capacities and states, and request-specific characteristics, edge inference scheduling must be request-dependent, state-aware, and time-varying, rather than static and one-shot. Although recent studies advanced edge LLM inference through efficient batching, task offloading, and resource allocation [4]–[6], critical issues closely tied to practical edge LLM inference remain insufficiently explored. On one hand, unlike conventional edge-computing requests abstracted as atomic tasks completed within a single scheduling slot, LLM inference requests may remain active across multiple slots. During this period, subsequent requests continue to be scheduled and arrive, causing their service processes to overlap and interact through shared edge server resources. For example, an edge server supporting multiple agentic-AI-driven mobile robots may receive a new reasoning request from one robot while still generating a response for another. Admitting the new request changes the allocation of shared inference resources, thereby affecting the completion time of ongoing inference. Such interactions persist across scheduling slots, contrasting with conventional scheduling paradigms [7]–[9], where decision outcomes are immediately observed to guide the decision in the next time slot. Therefore, LLM scheduling exhibits crossrequest and cross-slot effects that most studies fail to capture: assigning a new request without accounting for unfinished ones prolongs latency, but this impact becomes observable only after the affected requests complete several slots later. This requires the scheduler to make sequential decisions before the outcomes of previous ones are revealed. On the other hand, many inference scheduling studies prioritize latency while overlooking load imbalance among edge servers. A scheduler may continuously route requests to a high-capability server, gradually pushing it toward resource limits. For LLM serving, such saturation is particularly risky because each admission decision creates a stateful resource commitment on the edge server. Since a request’s resource demand continuously grows during response generation, redirecting new arrivals cannot immediately relieve an already saturated server. This concentration leaves servers vulnerable to lengthy requests, traffic bursts, or scheduling errors, and such localized pressure could be amplified into system-wide taillatency inflation and throughput loss, degrading the quality-of-
2
service (QoS) of heavily loaded servers while leaving lightly loaded ones under-utilized [10], [11]. Load balancing is thus not merely about resource utilization, but a vital long-term risk dispersion requirement missed by latency-only schedulers. However, edge LLM inference scheduling introduces three key challenges. First, evaluating end-to-end latency requires modeling a request’s complete lifecycle across wireless transmission and the inference pipeline, including batching, prefill, and decoding stages. Emerging LLM serving techniques such as continuous batching [12], [13] further allow requests to dynamically join or leave active batches, introducing complex dependencies that make realistic LLM inference substantially harder to model and analyze than conventional edge tasks. Second, conventional indicators like queue length cannot fully reflect actual workloads, as requests with diverse input/output token lengths consume varying inference resources over different duration. It is necessary to map this resource consumption to a workload metric that also accounts for heterogeneous server capabilities [14]. Load balancing therefore relies on a metric capable of jointly capturing the intensity and duration of resource occupation across diverse requests and edge servers. Third, jointly addressing delayed latency feedback and longterm load balancing poses a further challenge. The end-to-end latency impact of a scheduling decision remains unobservable until the inference request completes, leaving the scheduler without a timely learning signal [15]. Meanwhile, load balancing depends on workloads accumulated across slots and cannot be enforced by penalizing isolated decisions. This mismatch substantially complicates scheduler design. To address these challenges, in this paper, we model each request’s inference lifecycle and server-side resource occupation at a fine granularity, formulating an online scheduling problem that minimizes end-to-end latency subject to peak-memory feasibility and long-term load-balancing constraints. This problem is difficult to solve due to its longterm constraints, request-server heterogeneity, and cross-slot delayed feedback. We propose a Lyapunov-guided rewardredistribution online request scheduling (LYREO) approach that jointly addresses these difficulties through constraintaware long-term guidance and delayed-feedback-aware policy learning. The main contributions are summarized as follows. • We develop a fine-grained model that captures edge LLM inference throughout transmission, batching, prefill, and iteration-level decoding. The model explicitly tracks the evolution of the key-value (KV) cache occupation on each edge server driven by unfinished requests and continuous batch updates, thereby quantifying how each assignment reshapes serving conditions and end-to-end latency. • Building on this KV cache trajectory, we characterize each server’s workload using a normalized KV cache memory-time consumption metric that jointly reflects memory intensity and active duration. Based on this metric, we formulate the long-term end-to-end latencyminimization problem subject to peak memory feasibility and inter-server load-balancing constraints. • We put forth a novel approach, named LYREO, to address this optimization problem. LYREO leverages Lyapunov virtual queues to adaptively satisfy long-term load-
balancing constraints. To effectively learn from delayed feedback, LYREO employs a long short-term memory (LSTM)-based reward redistribution mechanism, supported by sequence truncation and value bootstrapping, to provide timely learning signals for online policy learning. • We evaluate the proposed LYREO approach across diverse system and algorithm configurations. The results show consistent improvements in end-to-end latency and load-balancing deviation over the baseline approaches. The rest of this paper is organized as follows. Section II reviews related work and highlights the novelty of this paper. Section III presents the system model and problem formulation. Section IV presents LYREO and provides its theoretical analysis. Section V reports and discusses the evaluation results, and Section VI concludes the paper. II. R ELATED W ORK Recently, numerous studies have improved LLM inference serving through batching, scheduling, and memory management. Orca [12] introduced iteration-level scheduling, which executes LLM inference at the granularity of individual tokengeneration iterations rather than complete requests. vLLM [13] introduced PagedAttention to dynamically manage the KV cache of requests with varying lengths. Together, these techniques establish the foundation of continuous batching, substantially improving GPU utilization and latency for agentic AI applications [16]. Nonetheless, they primarily optimize inference engines or tightly connected accelerator clusters, leaving wireless transmission, time-varying user connectivity, and request assignment across geographically distributed edge servers outside the scheduling process. Some recent studies have extended LLM inference to mobile edge networks. The wireless edge LLM inference framework in [17] integrates request batching and model quantization, and jointly optimizes batch scheduling and resource allocation to maximize inference throughput under heterogeneous latency and accuracy requirements. In [6], a two-timescale framework was introduced to coordinate slow-timescale LLM deployment with fast-timescale batch scheduling, GPU resource allocation, and bandwidth allocation in edge-cloud networks to minimize energy cost and end-to-end latency. Additionally, [18] proposed a collaborative inference framework that jointly selects distributed devices and partitions the LLM into deployable shards to reduce inference latency and improve throughput. Nevertheless, these studies generally treat each inference request as a conventional atomic task with simplified latency models, failing to capture the multi-stage and cross-slot dynamics of practical LLM serving. Load balancing remains comparatively underexplored in edge LLM inference. A recent framework in [19] combined workload prediction with reinforcement learning in scheduling to reduce inference latency and balance GPU utilization across edge LLM instances. CoLLM [20] enabled collaborative LLM inference across resource-constrained devices to reduce inference latency while balancing energy consumption. However, these load-aware methods typically overlook time-integrated resource occupation, and long-term load balancing of heterogeneous requests and edge servers remains largely unexplored.
3
Navigating
S Coding
LLM Inference
Timeline 𝑡
Service Scheduler t es qu e R
1 2
g in ul ed h c
Prefill
𝑡+1
Δ
Decoding
3
① Prefill Phase:
Batched Prefill
Prompts Q (𝑡) Arrival !
Wireless Communication
Dynamic Entry-and-Exit Decoding
② Decoding Phase: Edge Server 1
Edge Server 𝑠
Iteration 𝑘
1 2
𝑘+ ! (𝑡)
𝐾! (𝑡)
!"!#$%
Manipulating
Agentic AI Service
#$% 𝐵", 𝑣" , 𝑣"&%' (·)
#$%
𝐵( , 𝑣( , 𝑣(&%' (·)
𝑖 ∈ 𝑄! (𝑡) 1 2 … 𝑘 … "#
𝑗 ∈ 𝑄! (𝑡)
"#$
1 … 𝑙! … 𝑘 … "#$ %&' 1 … 𝑙! … 𝑙%!
Request Departure
KV Cache Size
Memory 𝑀!
Iteration
Fig. 1: System model of the edge-assisted LLM inference framework. To improve performance in edge LLM inference, recent studies have widely applied deep reinforcement learning (DRL) [21]–[23] and Lyapunov optimization [24], [25] to coordinate request scheduling, offloading, and resource allocation. Nonetheless, these studies rely on per-slot system observations and immediately available performance signals, without explicitly addressing the delayed nature of inference feedback. Consequently, how to attribute delayed outcomes to their causal scheduling decisions remains an open problem. Unlike prior studies, this paper jointly models the cross-slot, multi-stage execution of edge LLM inference and characterizes the resulting edge server workload. Furthermore, we develop a Lyapunov-guided reward-redistribution online scheduling approach that resolves the delayed feedback while maintaining long-term load balance across heterogeneous edge servers. To our knowledge, these coupled issues have not been jointly addressed in previous work. III. S YSTEM M ODEL & P ROBLEM F ORMULATION In this section, we first present an overview of the considered edge-assisted LLM inference system in Section III-A. Sections III-B–III-D then detail the communication, LLM inference, and memory models, respectively. Finally, Section III-E formulates the corresponding optimization problem. A. System Overview As illustrated in Fig. 1, the edge LLM-based agentic AI system comprises an LLM service scheduler, multiple mobile users, and a set of edge servers denoted by S = {1, 2, . . . , S}. The system operates in equal discrete time slots t ∈ T = {1, . . . , T } of length ∆ seconds. Let U = {1, . . . , U } denote the set of subscribed mobile users with time-varying locations. These mobile users represent devices running LLM-powered agentic applications, whose reasoning invocations are served by shared edge-hosted models. Operating at the inferenceservice layer, we represent these application-generated invocations using a slotted request model. Specifically, at the beginning of each time slot t, every user u ∈ U generates one inference request, indexed by i = (u, t). The inference requests generated by users in time slot t are collected in set Q(t) = {(u, t) | u ∈ U}. Each request i ∈ Q(t) is characterized by a tuple ⟨liin , ˆliout , oi ⟩, where liin ∈ Z+ and ˆliout ∈ Z+ are the input and output token lengths, respectively. Here, ˆliout is
treated as a known input, whether user-specified or estimated via existing methods [21]. oi ∈ R2 denotes the geographical coordinates of the user when generating request i. The scheduling decision is denoted by xi,s (t) ∈ {0, 1}, where xi,s (t) = 1 indicates that request i ∈ Q(t) is assigned to edge server s, and xi,s (t) = 0 otherwise. The decisions are made by the service scheduler at the beginning of each time slot, based on the collected request metadata. To reflect practical LLM inference systems, we do not assume edge servers are idle at scheduling time, i.e., they may still be processing backlogged requests from previous time slots. Let Qs (t) = {i ∈ Q(t) | xi,s (t) = 1} be the subset of requests scheduled to edge server s in time slot t. These requests are then transmitted to the edge servers and processed accordingly, as detailed in Sections III-B and III-C. Upon completion, the inference results are returned to the users. B. Communication Model Following the scheduling decisions, users transmit their input request tokens to the assigned edge servers via wireless links. Let Bs denote the total bandwidth of edge server s, which is equally shared among all requests scheduled to it. For request i ∈ Qs (t), the transmission rate is given by pi hi,s (t) Bs log2 1 + , (1) Ri,s (t) = |Qs (t)| N0,s Bs /|Qs (t)| where N0,s is the noise power spectral density (PSD) at edge server s, and pi denotes the transmission power of the user generating request i. hi,s (t) denotes the channel gain between the user and edge server s, modeled as a function of the distance ∥oi − os ∥ [26], where os is the location of edge server s. Then, the transmission delay of request i is given by tx Di,s (t) =
βliin , Ri,s (t)
(2)
where β (in bits) is the data size of a single token. Since inference computation begins only after all scheduled prompts have been received [8], let Dssy (t) = tx maxi∈Qs (t) Di,s (t) be the synchronization delay for the batch at edge server s. Correspondingly, the waiting delay for request i is determined by the difference between this synchronization delay and its transmission time, which is given by wa tx Di,s (t) = Dssy (t) − Di,s (t).
(3)
4
Given that edge servers are equipped with significantly higher transmit power and wider downlink bandwidth compared to mobile users, the feedback latency after inference completion is considered negligible in this work. C. LLM Inference Model Modern LLMs rely on decoder-only transformer architectures, comprising prefill and decoding phases. In contrast to previous studies that simplify this process via static batching and single-slot completion, this work incorporates a highly realistic serving framework driven by continuous batching and iteration-level dynamics. The two phases are detailed below. 1) Prefill Phase: In the prefill phase, the input tokens are processed to compute the first output token and generate the corresponding KV cache. To fully exploit the parallel computing capability of GPUs, the tokens from multiple requests can be aggregated and processed simultaneously through largescale matrix multiplications [13]. Accordingly, all requests arriving at edge server s within time slot t, i.e., Qs (t), are grouped into a single batch for one forward-pass computation, known as batched prefill [17]. Since prefill is inherently compute-bound with relatively stable throughput, we assume its computation is independent of decoding tasks as long as sufficient KV cache memory is provisioned. Let vspre (in tokens/s) be the prefill rate of edge server s. The prefill latency of the batched requests scheduled to edge server s in time slot t is determined by the total number of input tokens and the edge server’s computational capability, expressed as [6], [27] P in i∈Qs (t) li pre . (4) Ds (t) = pre vs 2) Decoding Phase: In the decoding phase, the LLM generates output tokens autoregressively, producing one token per iteration until the output length is reached. At each iteration, the inference engine takes the previously generated token as input and performs computation based on the KV cache of all preceding tokens, which is updated incrementally as decoding proceeds. Unlike prefill, decoding iterations cannot be parallelized due to strict data dependencies. Consequently, despite minimal computation, decoding remains highly memorybound because it requires repeatedly loading model weights and the accumulated KV cache. We consider an advanced decoding mechanism enabled by iteration-level scheduling termed dynamic entry-and-exit decoding (DEED) [12], featuring: 1) early-finished eviction, where completed requests are removed from the batch and their KV cache is released immediately from memory at the end of iteration; and 2) latejoining admission, where new requests are admitted to the active batch and decoded together with backlogged requests, provided sufficient KV cache capacity is available. Based on the DEED mechanism, let Qbg s (t) be the set of backlogged requests remaining at the edge server s at the beginning of time slot t. Since the decoding phase typically dominates the end-to-end serving latency while the prefill latency is comparatively short [21], we assume, for a reasonable setting of ∆, all backlogged requests in Qbg s (t) have already completed the prefill phase (including transmission)
and remain only in the decoding phase. Let ljgen (t) be the cumulative number of generated tokens for request j ∈ Qbg s (t) at the beginning of slot t. While newly scheduled requests undergo transmission and prefill, the inference engine continues decoding these backlogged requests in Qbg s (t). Specifically, during the time budget Dssy (t)+Dspre (t), the KV cache memory occupied on the GPU of edge server s increases linearly with the generated tokens [16]. The KV cache memory occupation at the k-th decoding iteration in time slot t on edge server s can be derived as X mIs (k, t) = α (5) (ljin + ljgen (t) + k), j∈Gs (k,t)
where α is the per-token KV cache size1 , and Gs (k, t) = {j ∈ ˆout gen Qbg s (t) | k ≤ lj −lj (t)} denotes the set of active background requests at the k-th decoding iteration. The condition k ≤ ˆlout − lgen (t) in Gs (k, t) reflects the early-finished eviction of j j DEED, where the request is removed from the summation as its KV cache is released once decoding is complete. Denote the decoding throughput of edge server s (in steps/s) by vsdec (·), which is a function of the current total KV cache size. The time per decoding iteration on edge server s when mIs (k, t) > 0 is given by 1 , (6) τsI (k, t) = (1 − wIs (k, t)) · vsdec (mIs (k, t)) where Is (k, t) ∈ {0, 1} indicates the operational status of inference engine. Specifically, Is (k, t) = 0 when the server is in a pure decoding state, while Is (k, t) = 1 indicates the presence of concurrent prefill computation, which reduces the throughput by a fraction w ∈ (0, 1). Building on the periteration decoding time, the number of decoding iterations that can be completed on edge server s before the prefill phase finishes in time slot t can be determined by k n X τsI (κ, t) ≤ Dssy (t) + Dspre (t), k̃s (t) = max k (7) κ=1 o mIs (k, t) > 0 , where the condition mIs (k, t) > 0 ensures that the iteration counts only when there are backlogged requests to be decoded. Once the prefill phase finishes, the newly prefilled requests enter the decoding batch immediately through the late-joining admission mechanism of DEED2 . Let Hs (k, t) = {i ∈ Qs (t) | k − k̃s (t) ≤ ˆliout } denote the set of active new requests at the k-th decoding iteration. Therefore, the total KV cache size on edge server s can be calculated as X mIIs (k, t) = α (liin + k − k̃s (t)) i∈Hs (k,t)
+α
X
(ljin + ljgen (t) + k),
(8)
j∈Gs (k,t)
where the first term accounts for the KV cache of active newly scheduled requests, and the second term accounts for that 1 We approximate discrete KV cache allocation as continuous, as tail-block internal fragmentation is negligible relative to overall sequence lengths. 2 We ignore the sub-iteration waiting time for new requests to align with iteration boundaries, as it is negligible compared to the slot duration and overall inference latency.
5
of active backlogged requests. Note that both the mIs (k, t) and mIIs (k, t) are not necessarily monotonic with respect to k, as the early-finished eviction in DEED continuously removes completed requests and releases their KV cache, while the latejoining admission of new requests and the token generation of active requests increase the KV cache. Given the total KV cache size, the per-iteration decoding time and the number of iterations completed between prefill and the end of time slot t on edge server s can be respectively expressed as 1 , (9) τsII (k, t) = dec II vs (ms (k, t)) n k̄s (t) = max k
k X
τsII (k̃s (t) + κ, t) ≤ ∆ − Dssy (t)
κ=1
− Dspre (t),
mIIs (k̃s (t) + k, t) > 0
(10)
o .
Accordingly, for request i scheduled to edge server s in time slot t, the decoding latency is calculated by accumulating the per-iteration decoding latency over all output tokens, given by out
dec Di,s (t) =
l̂i X
′ τi,s (k),
(11)
k=1 ′ where τi,s (k) denotes the decoding time when generating the k-th output token of request i. Note that τsI (k, t), τsII (k, t), and ′ τi,s (k) represent the same physical quantity viewed from two ′ different perspectives: τi,s (k) tracks the per-iteration decoding time from the perspective of an individual request, whereas τsI (k, t) and τsII (k, t) characterize it along the system timeline in time slot t. Since the per-iteration decoding time along the ′ system timeline has been fully derived in (6) and (9), τi,s (k) can be directly obtained via the corresponding cross-slot index mapping, which is omitted here for brevity. For edge server s, the total number of completed decoding iterations within time slot t is the sum of iterations from both phases, which is given by Ks (t) = k̃s (t) + k̄s (t). Therefore, the set of backlogged requests at the beginning of time slot t + 1 is updated as
ˆout Qbg s (t + 1) = {i ∈ Qs (t) | li > k̄s (t)} (12) ∪ {j ∈ Qbg (t) | ˆlout > lgen (t) + Ks (t)}, s
j
j
where the first term represents the newly scheduled requests in Qs (t) that have not been completed by the end of time slot t, and the second term represents the previously backlogged requests in Qbg s (t) that remain unfinished. In contrast to the conventional “clear-then-schedule” assumption, here we do not require all requests to be completed within the current time slot, which more faithfully reflects the realistic operation of LLM inference systems. D. Memory Analysis Unlike traditional computing tasks, LLM serving, especially the dominant autoregressive decoding, is inherently stateful and frequently bottlenecked by memory-resource availability. Since the KV cache footprint strongly affects the achievable decoding throughput and serving capacity, KV cache occupation is explicitly modeled as a key resource state [13], [28].
Based on the system workflow described above, the KV cache occupation at the k-th decoding iteration in time slot t on edge server s can be unified as ( mIs (k, t), 1 ≤ k ≤ k̃s (t), (13) ms (k, t) = mIIs (k, t), k̃s (t) < k ≤ Ks (t). Let Ms be the GPU memory capacity of edge server s reserved for KV cache during LLM inference. To ensure feasibility, the peak KV cache occupation must not exceed the available memory capacity throughout the inference process, Mspk (t) =
max k=1,...,Ks (t)
ms (k, t) ≤ Ms .
(14)
Note that the peak memory constraint defined above naturally unifies two feasibility requirements. First, it ensures that the KV cache memory does not overflow during the autoregressive decoding phase as tokens are incrementally generated. Second, it acts as an admission feasibility condition for newly scheduled requests, ensuring that sufficient GPU memory is available for the KV cache generated during prefill. As a result, admitted requests can start the prefill phase immediately after batching, without incurring additional engine-level waiting. In addition to acting as a hard feasibility constraint, the KV cache occupation on edge servers reflects the continuous inference workload, as it remains persistently allocated throughout the inference lifecycle and continuously consumes GPU memory resources. Accordingly, we define the workload of edge server s in time slot t as the normalized KV cache memory-time consumption, i.e., PKs (t) ms (k, t)τs (k, t) , (15) ηs (t) = k=1 Ms ∆ where the unified per-iteration decoding time at the k-th iteration on edge server s within time slot t is given by ( τsI (k, t), 1 ≤ k ≤ k̃s (t), (16) τs (k, t) = τsII (k, t), k̃s (t) < k ≤ Ks (t). In (15), the numerator accumulates the memory occupied at each decoding iteration weighted by its duration, measuring the cumulative KV residency incurred by the inference engine, while the denominator represents the maximum available memory-time capacity of the edge server within a slot. By jointly integrating the spatial and temporal dimensions of KV cache occupation, ηs (t) effectively captures the KV-centric workload pressure, particularly across heterogeneous edge servers. In the spatial dimension, normalizing the occupation by the total capacity Ms ensures that the same KV cache size imposes a much heavier load on edge servers with scarce memory. In the temporal dimension, under an identical KV cache state, edge servers with weaker processing capabilities exhibit longer per-iteration decoding times τs (k, t), incurring a larger value of the memory-time consumption term in our metric. This dual sensitivity allows ηs (t) to characterize the heterogeneous load distribution, providing a tractable and interpretable indicator of LLM inference workload. E. Problem Formulation In summary, the end-to-end latency for request i scheduled to edge server s in time slot t, consisting of the transmission,
6
batch waiting, prefill, and decoding latency, is formulated as tot tx wa dec Di,s (t) = Di,s (t) + Di,s (t) + Dspre (t) + Di,s (t).
(17)
Beyond latency, load balance across edge servers is also considered to maintain the workload deviation within acceptable bounds. To ensure long-term load balance, the variancebased workload deviation of each edge server s ∈ S from the system average must satisfy the following constraint T
2 1X (18) ηs (t) − η̄(t) ≤ ϵ, ∀s ∈ S, T →∞ T t=1 P where η̄(t) = S1 s∈S ηs (t) denotes the average workload over all edge servers in time slot t and ϵ denotes the predefined long-term tolerance threshold. With the objective of minimizing the long-term timeaverage end-to-end latency of all inference requests while ensuring load balance across edge servers, we formulate an online optimization problem over the scheduling decision x(t) = {xi,s (t) | ∀i ∈ Q(t), ∀s ∈ S} for each time slot t ∈ T . The problem is formally stated as lim
T i 1X h X X tot xi,s (t)Di,s (t) , (19a) E {x(t)} T →∞ T t=1
P1 : min lim
i∈Q(t) s∈S
s.t. (18), Mspk (t) ≤ Ms , ∀s ∈ S, ∀t ∈ T ,
(19b)
xi,s (t) ∈ {0, 1}, ∀i ∈ Q(t), ∀s ∈ S, ∀t ∈ T , X xi,s (t) = 1, ∀i ∈ Q(t), ∀t ∈ T ,
(19c) (19d)
s∈S
where constraint (18) specifies the long-term average loadbalancing constraint. Constraint (19b) ensures that the KV cache occupation at each edge server does not exceed its available memory capacity, guaranteeing the feasibility of LLM inference execution. Constraints (19c) and (19d) enforce the binary nature of the scheduling variables and the unique assignment of each request to an edge server, respectively. Solving problem P1 directly is nontrivial due to the following complexities. Fundamentally, the discrete scheduling decisions (i.e., x(t)) make the problem a nonlinear integer programming problem, which is known to be NP-hard. In addition, the attributes of inference requests (i.e., input/output token lengths) and the locations of mobile users vary over time in an a priori unknown manner, resulting in fluctuating inference workloads and time-varying channel conditions. Meanwhile, the heterogeneous prefill and decoding throughputs across edge servers further complicate the overall service latency. Last but not least, the scheduling decisions are coupled across time slots. The end-to-end latency of a request (i.e., tot Di,s (t)) depends not only on its own scheduling decision in time slot t, but also on the system state resulting from past scheduling decisions and the future system evolution driven by subsequent scheduling decisions. This temporal coupling, tot compounded by the fact that Di,s (t) only becomes observable after request completion, introduces strong interdependence between decisions across time, making the optimization problem particularly challenging.
IV. LYREO A PPROACH In this section, we develop LYREO, a novel approach that treats P1 as a sequential decision-making problem and jointly addresses the challenges identified above. Specifically, we first reformulate problem P1 by leveraging Lyapunov optimization to handle the long-term load-balancing constraint. We then introduce a reward redistribution mechanism to attribute delayed latency feedback to its associated decisions before optimizing the scheduling policy. Finally, we provide the theoretical analysis of the proposed approach. A. Problem Reformulation via Lyapunov Optimization Constraint (18) couples the scheduling decisions over the entire time horizon and therefore cannot be evaluated from the current time slot alone. To expose the accumulated load imbalance to each scheduling decision, we define a virtual queue for the workload deviation of each edge server, whose dynamics evolve as Zs (t + 1) = max{Zs (t) + Ys (t) − ϵ, 0}, s ∈ S,
(20)
2
where Ys (t) = (ηs (t) − η̄(t)) denotes the instantaneous workload deviation, and Zs (t) denotes the length of the virtual queue (with Zs (0) = 0), tracking the cumulative amount by which Ys (t) exceeds the threshold ϵ. Queue stability implies that the long-term workload deviation does not exceed ϵ, thereby satisfying constraint (18). Collecting the virtual queues of all edge servers, we define Z(t) = [Z1 (t), Z2 (t), . . . , ZS (t)] as the queue backlog vector in time slot t. To characterize how well the scheduling adheres to long-term load balancing, we define the following quadratic Lyapunov function [29] 1X Zs (t)2 . (21) L(Z(t)) ≜ 2 s∈S
A small value of L(Z(t)) indicates that all virtual queues are close to zero, i.e., the long-term constraint is well satisfied, and thus the system should aim to keep L(Z(t)) small. Then, the conditional Lyapunov drift is given by ∆(Z(t)) ≜ E [L(Z(t + 1)) − L(Z(t)) | Z(t)] ,
(22)
which represents the expected change in the Lyapunov function over time slots, and a smaller drift indicates a more stable queue. However, according to (22), the Lyapunov drift still depends on the system state in the next time slot, making it intractable to compute directly. To avoid relying on future system information, we derive an upper bound on the Lyapunov drift, as provided in Lemma 1. Lemma 1. The Lyapunov drift ∆(Z(t)) is upper bounded by hX i ∆(Z(t)) ≤ Γ + E Zs (t) (Ys (t) − ϵ) | Z(t) , (23) s∈S
2 where Γ ≥ s∈S E[(Ys (t) − ϵ) ] /2 is a positive constant that bounds the expected squared terms over all time slots. P
Proof. Squaring both sides of the virtual queue update in (20) and using the fact that {[x]+ }2 ≤ x2 for any x gives 2 Zs (t + 1)2 = [Zs (t) + Ys (t) − ϵ]+ (24) ≤ (Zs (t) + Ys (t) − ϵ)2 , s ∈ S.
7
Summing (24) over all s ∈ S and dividing by 2 yields 1X 1X 1X Zs (t + 1)2 ≤ Zs (t)2 + (Ys (t) − ϵ)2 2 2 2 s∈S s∈S s∈S (25) X + Zs (t)(Ys (t) − ϵ). s∈S
2 Subtracting /2 from both sides and incors∈S Zs (t) porating the conditional expectation with respect to Z(t), the upper bound for ∆(Z(t)) can be derived as h1 X i 1X Zs (t + 1)2 − Zs (t)2 | Z(t) ∆(Z(t)) = E 2 2 s∈S s∈S i h1 X X (Ys (t) − ϵ)2 + Zs (t)(Ys (t) − ϵ) | Z(t) . ≤E 2 s∈S s∈S (26) Substituting the definition of Γ into the preceding inequality yields (23), which completes the proof. P
Lemma 1 provides an upper bound on the Lyapunov drift that no longer explicitly depends on the future virtual-queue state. Based on the Lyapunov optimization framework, the objective function of the original problem P1 can be rewritten as the minimization of the following drift-plus-penalty function, h X X i tot ∆(Z(t)) + νE xi,s (t)Di,s (t) | Z(t) i∈Q(t) s∈S
≤Γ+E
hX
i Zs (t) (Ys (t) − ϵ) | Z(t)
(27)
h s∈S i X X tot + νE xi,s (t)Di,s (t) | Z(t) , i∈Q(t) s∈S
where ν > 0 is a control parameter that balances the trade-off between minimizing end-to-end latency and maintaining longterm load balance. By dropping terms independent of x(t), we obtain the following per-slot reformulation of problem P1, h X X tot P2 : min E ν xi,s (t)Di,s (t) x(t)
i∈Q(t) s∈S
+
X
i Zs (t)Ys (t) | Z(t) ,
(28)
s∈S
s.t. (19b), (19c), (19d). Note that, in problem P2, the long-term load-balancing constraint of P1 has been transformed into a per-slot corrective term. However, P2 remains intractable, mainly because tot the latency term Di,s (t) in the objective depends on future system information. Specifically, the scheduling decision must be committed in the current time slot, whereas the resulting end-to-end latency can only be observed after inference completion, and is further influenced by the arrival and scheduling of subsequent requests assigned to the same edge server. To this end, in the next subsection, we propose a novel policy learning framework to efficiently address this challenge. B. Delayed-Feedback-Aware Policy Learning 1) Sequence-Markov Decision Process Formulation: Problem P2 constitutes a sequential decision-making process, as each scheduling action updates the system states encountered
by subsequent decisions. Accordingly, we formulate it as a sequence-Markov decision process (SDP), represented by the tuple ⟨S, A, P, R, γ⟩, where, unlike a standard Markov decision process, the rewards are not required to satisfy the Markov property. At each time step t, the scheduler observes the current state st ∈ S and takes an action at ∈ A, which transitions the environment to a new state st+1 with probability Pr[st+1 | st , at ] and returns a reward rt+1 ∈ R. The discount factor γ ∈ (0, 1) balances the immediate and future rewards. The detailed definitions of the state and action space, and reward function are provided as follows. • State Space. The state represents the system information available to the scheduler in each time slot t, defined as ser st = {sreq t , st },
(29)
where sreq = [liin , ˆliout , oi ]i∈Q(t) denotes the attributes t of the inference requests to be scheduled, and sser = t [Bs , vspre , vsdec (c), |Qbg s (t)|, ηs (t − 1), Zs (t)]s∈S denotes the server-side state information, including the attributes (i.e., bandwidth, prefill and decoding throughput) and the dynamic status (i.e., the number of backlogged requests, the recent workload, and the virtual-queue length of load-balancing deviation) of each edge server. Here, vsdec (c) denotes the decoding throughput evaluated at a constant reference occupation c, serving as an indicator of the server’s decoding capability. • Action Space. In each time slot t, the scheduler determines the scheduling decision for all requests in Q(t). The action is defined as at = x(t) = {xi,s (t) | ∀i ∈ Q(t), ∀s ∈ S}. • Reward Function. By taking action at under state st , the scheduler receives a numerical reward defined according to the objective function in (28), given by X X X tot rt+1 = −ν Di,s (t)− Zs (t)Ys (t)−ϱΥ(t), (30) s∈S i∈Q′s (t)
s∈S
where Q′s (t) represents the set of requests that complete their on edge server s in time slot t. Υ(t) = P inference pk (t) − Ms ]+ is a penalty term enforcing the GPU [M s s∈S memory constraint, and ϱ > 0 is the corresponding penalty coefficient. Overall, the reward jointly incorporates the total latency of requests, the load-balancing deviation captured by the virtual queue, and the memory feasibility penalty. 2) Reward Redistribution: As discussed above, the latency term in (30) introduces delayed rewards into the framework, so the scheduler cannot immediately evaluate which earlier assignment caused the eventual outcome. Inspired by [30], we introduce reward redistribution to recover a decision-level reward signal. Reward redistribution PT is a procedure for an SDP that redistributes the total return t=0 rt+1 over the sequence of state-action pairs (s0 , a0 , . . . , sT , aT ). Since reward redistribution preserves the cumulative return of the sequence, the expected return under any policy remains unchanged. Therefore, the original SDP and the redistributed SDP share the same optimal policy, indicating that reward redistribution does not alter the underlying optimization objective. Following the optimal second-order Markov reward redistribution in [30]–[32], we consider a reward signal that satisfies ′ E[rt+1 | χt−1 , χt ] = q π (χt ) − q π (χt−1 ),
(31)
8
where χt = (st , at ) and q π (χt ) denote the state-action pair in time slot t and its corresponding Q-value under policy π, respectively. Since the Q-value represents the expected cumulative return starting from a given state-action pair, Eq. (31) implies that the redistributed reward mathematically captures the increment in the expected return brought by the current state-action pair. By immediately assigning this increment to that pair, the expected future redistributed reward becomes zero, which eliminates reward delay in expectation. Consequently, this formulation provides a step-wise objective for policy learning. To illustrate this intuitively, if a state-action pair increases the cumulative return, i.e., q π (χt ) > q π (χt−1 ), ′ the corresponding redistributed reward rt+1 becomes positive, even though this improvement may not be reflected immediately in the original delayed reward. Although the second-order Markov reward redistribution is theoretically optimal for finite-horizon problems, it relies on predicting the cumulative return associated with each observed state-action sequence. In finite-horizon settings, the complete sequence return naturally serves as the supervision target for this prediction. However, under an infinite-horizon formulation, the complete sequence return is unavailable. To overcome this limitation, we develop a novel infinite-horizon return prediction framework by integrating sequence truncation with value bootstrapping. Specifically, instead of using the complete sequence return as the supervision target, we construct a return target that combines the actual rewards observed up to a truncation point H with a bootstrapped estimate for the remaining horizon. We define this return target as ŷH ≜
H−1 X
γ h rh+1 + γ H Vϕ (sH ),
(32)
h=0
where the first term is the cumulative discounted reward over the first H steps, i.e., the original infinite-horizon trajectory is truncated after H steps, while the second term is a bootstrap estimate of the remaining discounted return, provided by the value network introduced later. Since this return prediction requires estimating the expected return conditioned on variable-length state-action sequences, we employ an LSTM network, parameterized by ψ and denoted by gψ (·), which is well-suited for modeling such sequential dependencies. Given the sequence observed up to time slot t, the network outputs a prediction gt ≜ gψ (χ0:t ) ≈ E[ŷH | χ0 , . . . , χt ].
(33)
The network gψ (·) is then trained in a supervised manner by minimizing the mean-squared error (MSE) between gt and the truncated-bootstrapped target ŷH in (32). After training, the LSTM network serves as a return predictor that estimates the expected cumulative return from any observed state-action sequence. Given the sequence observed up to time slot t, the LSTM network outputs the corresponding prediction gt . The redistributed reward is then computed as ′ rt+1 = gt − gt−1 ,
(34)
which measures the increment in the predicted return brought by the current state-action pair. Therefore, rewards are reassigned from delayed outcomes to the state-action pairs
that contribute to the eventual return, serving as a practical approximation of the theoretical reward redistribution in (31). 3) Scheduling Policy Optimization: The redistributed reward provides an immediate signal for learning how each observed system state should be mapped to request assignments. Accordingly, we parameterize the scheduling policy πθ (a | s) using a neural network with parameters θ, which outputs a categorical distribution over the edge servers for each incoming request. Also, we define a value network parameterized by ϕ to estimate the state value function Vϕ (s). Following proximal policy optimization (PPO) [33], we optimize these two networks as the actor and critic, respectively, eliminating the need for an explicit system transition model. To ensure stable policy updates, a surrogate objective function is utilized to constrain the optimization step by clipping the probability ratio between the new and old policies. Let ρt (θ) = πθ (at |st )/πθold (at |st ) denote the probability ratio between the new and old policy. The surrogate objective function is defined as LCLIP (θ) = Et min ρt (θ)Ât , clip(ρt (θ), 1 − ε, 1 + ε)Ât , (35) where ε is a clipping hyperparameter. Ât represents the advantage function, which quantifies the relative benefit of taking action at over the policy average. We apply P∞ generalized advantage estimation (GAE), given by Ât = l=0 (γλ)l δt+l , ′ where δt = rt+1 + γVϕ (st+1 ) − Vϕ (st ) denotes the temporaldifference (TD) error, and λ ∈ [0, 1] is a parameter of GAE. Accordingly, the actor network is updated by maximizing the surrogate objective function LCLIP (θ) using gradient ascent. Subsequently, the value network is trained by minimizing the MSE between the estimated state value and target value, LVF (ϕ) = Et [(Vϕ (st ) − V̂t )2 ],
(36)
where V̂t = Ât + Vϕold (st ) is the target value. The critic parameters ϕ are then updated via gradient descent on LV F (ϕ). C. Algorithm Summary and Theoretical Analysis The primary steps of LYREO are summarized in Algorithm 1. We now establish the theoretical performance guarantee of the proposed LYREO approach. Theorem 1. Let π ∗ denote an optimal policy of the delayedreward SDP induced by problem P2. Let π̂ denote the optimal policy learned by LYREO under the discount factor γ and truncation length H. Assume that the reward function is bounded by |rt | ≤ rmax , the value estimation error of the critic network is bounded by |V π (s) − Vϕ (s)| ≤ ϵv for any policy π, the conditional-mean regression error of the LSTMbased return predictor is bounded by |gt − E[ŷH | χ0:t ]| ≤ ϵr , and the policy optimization error of PPO is bounded by ϵPPO . The performance gap of the learned policy is bounded by 2γ H 4 H ∗ γ ϵv + rmax + ϵr + ϵPPO J(π ) − J(π̂) ≤ 1−γ 1−γ H γ ϵv + ϵr γ H rmax + + ϵPPO . =O 1−γ (1 − γ)2 (37) Proof. Let r′∗ denote the ideal untruncated redistributed reward derived from the true expected return under the optimal
9
Algorithm 1: LYREO Approach Input: Truncation length H; actor learning rate ξA ; critic learning rate ξC ; clipping parameter ε; discount factor γ; GAE parameter λ; PPO epochs Ξ Output: Learned scheduling policy πθ 1 Initialize actor network π, critic network V , and return predictor g with random parameters θ, ϕ, ψ; 2 while not converged do 3 Collect a batch of trajectories B = {(st , at , rt+1 , st+1 )}H−1 t=0 using policy πθ ; /* Reward Redistribution Learning */ 4 foreach trajectory in B do 5 Compute learning target ŷH via (32); 6 Construct training pairs {(χ0:t , ŷH )}H−1 t=0 ; 7
8 9 10 11 12 13 14
15
Update return predictor gψ by minimizing MSE between gψ (χ0:t ) and ŷH over all training pairs; /* Scheduling Policy Optimization */ Freeze return predictor gψ ; foreach trajectory in B do ′ Compute redistributed reward rt+1 via (34); Compute TD error δt and advantage Ât ; Set θold ← θ; for epoch = 1 to Ξ do Update actor parameters θ by maximizing LCLIP (θ) via (35) with learning rate ξA ; Update critic parameters ϕ by minimizing LVF (ϕ) via (36) with learning rate ξC ;
2γ H rmax ≜ Π. (40) 1−γ Step II: Bounding the Redistributed Reward Error. The LSTM network predicts the expected return conditioned on the state-action sequence χ0:t . Let gt∗ = E[y∞ | χ0:t ] and ĝt = E[ŷH | χ0:t ] denote the ideal prediction under the true return and the ideal conditional expectation of the truncatedbootstrapped target, respectively. Since |y∞ − ŷH | ≤ Π, Jensen’s inequality implies |y∞ − ŷH | ≤ γ H ϵv +
|gt∗ − ĝt | ≤ |E[y∞ − ŷH | χ0:t ]| ≤ E[|y∞ − ŷH | | χ0:t ] ≤ Π. (41) By assumption, the regression error between gt , trained via (33), and the conditional expectation ĝt is bounded by ϵr . Combining this with (41) via the triangle inequality, |gt∗ − gt | ≤ |gt∗ − ĝt | + |ĝt − gt | ≤ Π + ϵr .
(42)
Recalling the redistributed reward defined in (34), the error in the redistributed reward is bounded by ′∗ ′ ∗ |rt+1 − rt+1 | ≤ |gt∗ − gt | + |gt−1 − gt−1 | ≤ 2(Π + ϵr ), (43)
policy π ∗ . Based on the optimality of the second-order Markov reward redistribution established in [30], we consider the SDP guided by r′∗ as the ideal objective that provides immediate step-wise reward signals. The performance gap introduced by LYREO arises from approximating these ideal signals via sequence truncation and value bootstrapping in policy learning. We establish the bound in the following four steps. StepPI: Bounding the Return Prediction Error. Let ∞ y∞ = h=0 γ h rh+1 denote the true infinite-horizon cumulative return, and ŷH denote the approximated return constructed via truncation and bootstrapping, given by (32). The estimation error can be derived as ∞ X |y∞ − ŷH | = γ h rh+1 − γ H Vϕ (sH ) . (38) h=H
By adding and subtracting the same term γ H V π (sH ) and applying the triangle inequality, we obtain |y∞ − ŷH | ≤ γ H |V π (sH ) − Vϕ (sH )| ∞ X + γ h rh+1 − γ H V π (sH ) .
instantaneous reward is bounded by |rt | ≤ rmax , the absolute deviation between any realization of the truncated return and its expectation is bounded by 2γ H rmax /(1 − γ). Combining the two bounds, the return prediction error satisfies
(39)
h=H
By assumption, the first term is bounded by γ H ϵv . For the second term, by the definition of the value function, multiplying both sides by γ H P and re-indexing the summation, ∞ h we have γ H V π (sH ) = E h=H γ rh+1 | sH . Since the
′∗ ′ where rt+1 and rt+1 are the ideal redistributed reward and its approximation obtained via the proposed truncation and bootstrapping scheme, respectively. Step III: Bounding the Value Function Error. For any policy π, the difference between its value functions evaluated under the ideal and approximated redistributed rewards can be accumulated over the infinite horizon as "∞ # X π π t ′∗ ′ |Vr′∗ (s) − Vr′ (s)| = Eπ γ (rt+1 − rt+1 ) t=0 ∞ X
(44)
2(Π + ϵr ) . ≤ γ 2(Π + ϵr ) = 1−γ t=0 t
Step IV: Deriving the Policy Gap. We now evaluate the ∗ π̂ suboptimality of policy π̂r′ . Note that we have Vrπ′ − Vr′ r′ ≤ ϵPPO , as π̂r′ approximates the maximizer of the value function under r′ with a bounded optimization error ϵPPO . Leveraging the standard value difference decomposition then gives Jr′∗ (π ∗ ) − Jr′∗ (π̂r′ ) ∗
∗
π̂
π̂
≤ |Vrπ′∗ − Vrπ′ | + ϵPPO + |Vr′ r′ − Vr′∗r′ | (45) 2(Π + ϵr ) 2(Π + ϵr ) 4(Π + ϵr ) ≤ + ϵPPO + = + ϵPPO . 1−γ 1−γ 1−γ Substituting the definition of Π into the preceding inequality yields (37), which completes the proof. V. P ERFORMANCE E VALUATION A. Simulation Settings We consider a system consisting of heterogeneous edge servers. Each edge server deploys the Llama-3.2-1B model and is equipped with one of three GPU platforms: NVIDIA GeForce RTX 3080, RTX 3090, and RTX 4090. Following
Parameter
Value
Parameter
Value
Bandwidth Bs Transmission power pi Noise PSD N0,s Discount factor γ
[6, 14] MHz [15, 25] dBm −174 dBm/Hz 0.98
Clipping parameter ε Learning rate PPO training epochs Random seeds
0.2 3 × 10−4 10 5
Avg. End-to-End Latency (s)
TABLE I: Simulation Parameters
LYREO Ly-PPO PPO
7 6 5 4 3 2 0
the hardware specifications of these GPUs, the available GPU memory capacities are set to Ms ∈ {10, 20, 24} GB, respectively. The prefill rate vspre ∈ {2500, 4000, 8000} tokens/s and the decoding throughput vsdec (·) are obtained via offline profiling of the Llama-3.2 model using a vLLM-based serving engine on the corresponding GPU platforms. Specifically, vsdec (·) is modeled as a non-increasing function of the instantaneous KV cache occupation to reflect the memory-bound nature of the decoding phase. Inference requests are drawn from the LMSYS-Chat-1M dataset [34], with the input and output token lengths averaging 70 and 215 tokens, respectively. The KV cache memory occupation per token is set to α = 16 KB, while the transmission size of a single token is β = 16 bits. We set T = 800 time slots, slot duration ∆ = 1 s, and loadbalancing tolerance ϵ = 0.01. User locations evolve randomly within a 200 × 200 m2 service area in each time slot. During training, none of the algorithms has access to the complete trajectory. Instead, policy optimization relies only on the currently observed trajectory, consistent with the infinitehorizon formulation. After the T -th time slot, all unfinished inference requests continue execution until completion, and the rewards are accumulated and assigned to the final step. The neural networks are implemented using PyTorch 1.8. Both the actor and critic networks in the PPO architecture consist of four fully connected layers. The return predictor for reward redistribution is implemented as a two-layer LSTM with a hidden dimension of 64. The remaining parameters are summarized in Table I, following widely adopted settings from the literature [17], [19]. B. Baseline Approaches To comprehensively evaluate the proposed LYREO approach, we consider three categories of baseline schemes. First, two DRL-based baselines are implemented: the Lyapunov-assisted PPO algorithm (Ly-PPO) [22], which integrates Lyapunov optimization with PPO but excludes the proposed reward redistribution framework, and the conventional PPO algorithm (PPO) [23], which optimizes latency with the load-balancing constraint violation incorporated as a penalty term, without Lyapunov-based constraint transformation or reward redistribution framework. Second, to validate the effectiveness of the DEED architecture, we implement a static batching scheme (Static) [8], where inference requests are grouped into fixed batches for decoding: newly arrived requests are not admitted into an ongoing decoding batch, and completed requests remain until the entire batch finishes decoding. Finally, two heuristic scheduling strategies are included as classical non-learning baselines: Least-Loaded (LL), which schedules each request to the edge server with the
200
400
600
Episode (a)
800
1000
1200
Avg. Load-Balancing Queue Length
10
0.30 0.25 0.20 0.15 0.10 0.05 0.00 0
200
400
600
800
1000
1200
Episode (b)
Fig. 2: Convergence performance of LYREO, Ly-PPO, and PPO approaches. lowest current workload, and Random, which schedules each request to a randomly selected edge server. C. Performance Comparison and Analysis 1) Convergence Performance: Fig. 2 presents the convergence behavior of the three learning-based approaches regarding average end-to-end latency and load-balancing queue length. Solid curves and shaded regions represent the mean and min-max range across seeds, respectively. As shown in Fig. 2(a), LYREO achieves the lowest end-to-end latency throughout the training process and converges to a stable value of approximately 2.4 s. In comparison, Ly-PPO stabilizes at around 3.9 s, while conventional PPO converges to a substantially higher latency of approximately 5.2 s. Fig. 2(b) shows a consistent performance advantage in load-balancing control. After convergence, LYREO reduces the average load-balancing queue length to approximately 0.02, compared with about 0.09 for Ly-PPO and 0.22 for PPO (computed post hoc). Moreover, the two Lyapunov-guided approaches maintain relatively stable queue levels, whereas PPO remains at a higher and more variable plateau. The improvement of LYREO over Ly-PPO highlights the benefit of reward redistribution. By attributing delayed inference outcomes to the scheduling decisions responsible for them, LYREO provides more informative temporal feedback for policy learning, leading to the best overall convergence performance. This benefit extends beyond latency: since load balancing is incorporated into the drift-plus-penalty function, the same mechanism also helps the policy associate accumulated imbalance with the scheduling decisions, improving the load-balancing component. Meanwhile, the gap between PPO and the two Lyapunov-guided approaches demonstrates the advantage of incorporating the Lyapunov framework into policy learning. Although PPO also penalizes excessive workload deviation, its balancing pressure does not adapt to the accumulated deviation over time. In contrast, the Lyapunov virtual queue provides an adaptive corrective signal, resulting in lower and more stable load-balancing queue lengths. 2) Distribution Comparison: Fig. 3 examines the distributions of the two performance metrics over the evaluation runs. In Fig. 3(a), LYREO achieves the lowest median end-to-end latency and the most compact distribution, followed by Ly-PPO, whereas PPO, Static, LL, and Random exhibit higher medians and longer upper tails. Fig. 3(b) shows that LYREO and LyPPO maintain lower load-balancing deviations than the other
Avg. End-to-End Latency (s)
12 10 8 6 4 2 LYREO Ly-PPO PPO
Static
(a)
LL
Random
Avg. Load-Balancing Deviation (×10−2 )
11
TABLE II: Load-Balancing and Workload Metrics Ablation
3.5 3.0
Approach
2.5 2.0
LYREO
1.5 1.0
LYREO-Count
0.5
LYREO-NoLB LYREO Ly-PPO PPO
Static
(b)
LL
Avg. End-to-End Avg. Load-Balancing P99 End-to-End High-KV Latency (s) Deviation (×10−2 ) Latency (s) Ratio (%) 2.63
0.8
3.74
(Ref.)
(Ref.)
(Ref.)
6.42 (Ref.)
2.79
1.1
4.56
8.04
(+6.1%)
(+37.5%)
(+21.9%)
(+25.2%)
2.02
1.8
6.73
14.35
(−23.2%)
(+125.0%)
(+79.9%)
(+123.5%)
Random
Fig. 3: Boxplot comparison of different approaches. baselines. Overall, the consistent advantages of LYREO and Ly-PPO demonstrate the efficacy of handling load-balancing constraints through adaptive Lyapunov guidance. On the other hand, PPO outperforms most non-learning baselines across the two metrics, indicating that the penalty term enables it to learn a meaningful trade-off between latency and load balancing. However, treating load balancing as a fixed penalty limits its ability to adapt to time-varying server imbalance. Also, the delayed feedback associated with the penalty causes PPO to react only after requests have accumulated on particular edge servers, leading to worse performance than LYREO and LyPPO. Among the non-learning baselines, Static achieves lower latency than LL, whereas LL provides better load balancing. Random performs worst on both metrics, exhibiting the highest medians and the widest distributions. D. Load-Balancing Ablation This subsection evaluates the necessity of long-term load balancing and validates the KV cache memory-time consumption workload through two variants of LYREO for the ablation study. Specifically, LYREO-Count replaces the proposed KV cache memory-time consumption with the number of active requests, while LYREO-NoLB removes the long-term loadbalancing constraint. Beyond the two primary optimization objectives, we introduce two additional evaluation metrics: the P99 end-to-end latency, defined as the 99th percentile of request-level latency, and the high-KV ratio, defined as the percentage of time slots across all edge servers where the peak KV cache utilization exceeds 90% of the reserved memory capacity limit. These two metrics, which are not directly optimized by the considered approaches, respectively characterize the worst-case, user-perceived latency that governs QoS satisfaction and the frequency of near-limit KV cache operation in edge servers, providing complementary evidence for the system-level performance of scheduling approaches. As shown in Table II, LYREO-NoLB achieves the lowest average end-to-end latency, since it is free to concentrate inference requests on the servers offering the lowest latency. However, this latency advantage is accompanied by the cost of less balanced resource utilization. Without the load-balancing mechanism, request concentration drives the average loadbalancing deviation up by 125.0% relative to LYREO, while the high-KV ratio rises to 14.35%, a 123.5% relative increase. More importantly, this imbalance translates into substantially worse tail behavior, with the P99 end-to-end latency reaching 6.73 s, 79.9% higher than that of LYREO. These results show
that latency-oriented scheduling alone cannot prevent persistent workload concentration. Explicit long-term load balancing instead preserves KV cache headroom across edge servers and mitigates the tail-latency degradation, at the expected cost of higher average latency. Meanwhile, LYREO-Count consistently underperforms LYREO across all four metrics, increasing the average latency to 2.79 s, the P99 latency to 4.56 s, the average load-balancing deviation to 0.011, and the high-KV slot ratio to 8.04%. This indicates that conventional count-based balancing does not balance the resource pressure imposed on heterogeneous edge servers, since inference requests differ in their KV cache occupation and duration. By jointly capturing occupation and residence time, the KV cache memory-time consumption provides a more reliable workload signal, validating its design for long-term load-balancing. 1) Impact of System Parameters: Fig. 4 presents the impact of the number of users on algorithm performance, with the number of edge servers fixed at S = 8. Since each user generates one request per time slot in our system, U directly determines the inference request intensity within each time slot. Fig. 4(a) illustrates that the average end-to-end latency of all methods increases as U grows from 20 to 60, since more users generate more requests within each time slot, which share the limited wireless bandwidth and result in larger prefill and decoding batches. The latency of LYREO increases from about 2.3 s to 3.3 s, while the second-best Ly-PPO rises from about 2.9 s to 5.6 s. On average, LYREO therefore reduces latency by roughly 33% relative to Ly-PPO, with an even larger gap relative to PPO, Static, LL, and Random. Fig. 4(b) shows that heavier traffic also increases the server-averaged load-balancing deviation of all schemes. Nevertheless, LYREO keeps the deviation below approximately 0.009 for the entire tested range, satisfying the predefined tolerance on average. Overall, LYREO consistently achieves the best performance across both metrics, and its advantage widens significantly under high request intensity. This is because heavier request intensity prolongs request completion, leading to more delayed rewards, a setting in which reward redistribution is particularly effective and consequently amplifies the advantage of LYREO over Ly-PPO. Meanwhile, higher intensity pushes the system closer to its capacity limit, where minor allocation imbalances can rapidly accumulate into substantial workload disparities. The Lyapunov virtual queue resolves this by proactively regulating workload imbalance, allowing LYREO to yield its advantage over LL, PPO, and other baselines. Fig. 5 compares system performance with respect to the number of edge servers, with the number of users fixed at U = 40. Increasing S provides more transmission bandwidth, computation capacity, and KV cache capacity, so all
12
Ly-PPO
PPO
14 12 10 8 6 4 2
20
30
40
50
Number of Users U
60
Static Avg. Load-Balancing Deviation (×10−2 )
Avg. End-to-End Latency (s)
LYREO
LL
Random
3.0 2.5 2.0 1.5 1.0 0.5 20
30
40
50
Number of Users U
(a)
60
(b)
Fig. 4: Performance comparison under varying numbers of users. Ly-PPO
PPO
12 10 8 6 4 2 6
7
8
9
Number of Edge Servers S
(a)
10
Static Avg. Load-Balancing Deviation (×10−2 )
Avg. End-to-End Latency (s)
LYREO
LL
Random
2.8 2.4 2.0 1.6 1.2 0.8 6
7
8
9
Number of Edge Servers S
10
(b)
Fig. 5: Performance comparison under varying numbers of edge servers. algorithms achieve lower latency. From Fig. 5(a), LYREO consistently achieves the best latency performance across every server scale, followed by Ly-PPO and PPO. Among the non-learning methods, LL improves markedly as the number of servers increases, since least-loaded routing can select from a large pool of lightly occupied servers. Static shows only modest improvement, as its fixed batching strategy limits the benefit of additional servers, while Random remains the worst throughout, owing to its state-agnostic assignment. The loadbalancing deviations in Fig. 5(b) show no clear monotonic trend as the number of edge servers increases. Specifically, the learning-based approaches generally decrease at first and then flatten or slightly rebound. With a fixed number of requests, more edge servers mitigate workload concentration but also result in sparser per-server demand and a larger action space, making effective scheduling increasingly difficult. Nevertheless, LYREO maintains the lowest deviation across all settings, showing its stronger ability to exploit additional server choices while preserving system-wide load balance. Fig. 6 evaluates the impact of hardware heterogeneity under three distinct configurations: Homogeneous (Hom.) uses 8× RTX 3090 GPUs; Moderate (Mod.) uses 3× RTX 3080, 3× RTX 3090, and 2× RTX 4090 GPUs; and Heterogeneous (Het.) uses 4× RTX 3080, 1× RTX 3090, and 3× RTX 4090 GPUs. Average load-balancing deviation increases from Hom. to Mod. and Het. for every method, as growing heterogeneity in computational capacity across edge servers makes balanced workloads harder to maintain. Under the Hom. configuration, the three learning-based methods achieve the lowest deviations. As heterogeneity increases, LYREO and
Ly-PPO remain the two best-performing methods. LYREO consistently achieves the lowest deviation and remains slightly better than Ly-PPO, a small yet consistent advantage showing that reward redistribution improves not only latency but also load-balancing performance. LL performs best among the non-learning methods, a predictable outcome given that its routing is explicitly designed to correct current imbalances, thus providing a natural advantage in the deviation dimension. Static and Random perform worst under almost all configurations, as fixed batching and state-agnostic routing fail to adapt effectively to server heterogeneity. E. Hyperparameter Sensitivity Fig. 7 illustrates the latency-balancing trade-off of LYREO controlled by the Lyapunov parameter ν. Increasing ν from 0.05 to 2 places greater weight on the latency term in the drift-plus-penalty objective. Accordingly, end-to-end latency falls from about 5.6 s to 2.1 s, with most of the gain obtained by ν = 0.5, while the corresponding load-balancing deviation rises slowly at first and then increases from approximately 0.008 at ν = 0.5 to 0.016 and 0.019 at ν = 1 and 2, respectively. As expected, latency minimization comes at the cost of virtual-queue stabilization. Notably, ν = 0.5 marks a turning point in the trade-off: latency improvements become markedly less responsive to further increases in ν, whereas the load-balancing deviation grows increasingly sensitive. Finally, Fig. 8 shows the effect of the return predictor’s truncation length on LYREO’s average end-to-end latency. While all configurations converge, a longer H consistently yields a lower final latency. A larger H exposes the return predictor to more of the actual delayed reward, reducing its reliance on the bootstrapped estimation and yielding more accurate value predictions. This behavior matches our theoretical analysis of LYREO, where the policy performance gap shrinks as H increases. However, the improvement becomes marginal beyond H = 250, suggesting that most decision-relevant dependencies in the system can already be captured within a bounded horizon. Meanwhile, a longer truncation length extends the LSTM-based predictor’s recurrent trajectories, increasing training complexity. Consistent with this, H = 300 converges to a latency level close to that of H = 250 but exhibits larger fluctuations, indicating diminishing benefits and increased training instability. VI. C ONCLUSION This paper studied LLM inference request scheduling for agentic AI services, aiming to minimize long-term average end-to-end latency while maintaining load balance across heterogeneous edge servers. To capture fine-grained LLM serving processes, we developed a system model that jointly characterizes wireless transmission, multi-stage inference, and KV cache evolution throughout each request’s lifecycle. Based on this model, we quantified edge server workload using the normalized KV cache memory-time consumption and formulated a long-term load-balancing constraint. We proposed the LYREO approach, which converts accumulated load imbalance into per-slot scheduling guidance and redistributes delayed
PPO Static
LL Random
2.0 1.5 1.0 0.5 0.0
Hom.
Mod.
Avg. End-to-End Latency Avg. Load-Balancing Deviation
5.5
Het.
Configuration
Fig. 6: Performance comparison of load-balancing deviation under varying heterogeneity levels.
1.75
5.0 1.50
4.5 4.0
1.25
3.5
1.00
3.0 0.75
2.5 2.0
0.05
0.2 0.5 Lyapunov Parameter ν
1
2
0.50
Fig. 7: Impact of Lyapunov parameter on system performance.
outcomes to their responsible decisions, with sequence truncation and value bootstrapping enabling return estimation in the infinite-horizon setting. Extensive evaluations demonstrated that LYREO consistently reduces both end-to-end latency and load-balancing deviation, outperforming existing baselines. R EFERENCES [1] F. Jiang et al., “From large ai models to agentic ai: A tutorial on future intelligent communications,” IEEE J. Sel. Areas Commun., vol. 44, pp. 3507–3540, 2026. [2] C. Zhao et al., “Edge general intelligence through world models, large language models, and agentic ai: Fundamentals, solutions, and challenges,” IEEE Trans. Cogn. Commun. Netw., vol. 12, pp. 5649– 5675, 2026. [3] R. Zhang et al., “Toward edge general intelligence with agentic ai and agentification: Concepts, technologies, and future directions,” IEEE Commun. Surv. Tutor., vol. 28, pp. 4285–4318, 2026. [4] T. Zheng et al., “Joint optimization of dynamic batching and adaptive partitioning for distributed llms inference in mobile edge computing,” IEEE Trans. Mobile Comput., vol. 25, no. 6, pp. 8747–8763, 2026. [5] Y. He, J. Fang, F. R. Yu, and V. C. Leung, “Large language models (llms) inference offloading and resource allocation in cloud-edge computing: An active inference approach,” IEEE Trans. Mobile Comput., vol. 23, no. 12, pp. 11 253–11 264, 2024. [6] H. Huang et al., “Dynamic model deployment, batch scheduling, and resource allocation in mllm-enabled edge–cloud networks: A multiagent two-timescale drl approach,” IEEE Internet Things J., vol. 12, no. 23, pp. 50 818–50 835, 2025. [7] Y. Li, “Llm bandit: Cost-efficient llm generation via preferenceconditioned dynamic routing,” 2025. [Online]. Available: https: //arxiv.org/abs/2502.02743 [8] T. Li and Y. Gong, “Two-sided matching for batch-aware llm request scheduling in edge networks,” in Proc. IEEE 50th Conf. Local Comput. Netw. (LCN), 2025, pp. 1–7. [9] A. Mekrache, A. Ksentini, and C. Verikoukis, “Drl-enabled slo-aware task scheduling for large language models in 6g networks,” in Proc. IEEE Int. Conf. Commun. (ICC), 2025, pp. 813–818. [10] Z. Chen et al., “A universal load balancing principle and its application to large language model serving,” arXiv preprint arXiv:2601.17855, 2026. [11] C. Yi et al., “Workload re-allocation for edge computing with server collaboration: A cooperative queueing game approach,” IEEE Trans. Mobile Comput., vol. 22, no. 5, pp. 3095–3111, 2023. [12] G.-I. Yu, J. S. Jeong, G.-W. Kim, S. Kim, and B.-G. Chun, “Orca: A distributed serving system for transformer-based generative models,” in Proc. 16th USENIX Symp. Oper. Syst. Design Implementation (OSDI), 2022, pp. 521–538. [13] W. Kwon et al., “Efficient memory management for large language model serving with pagedattention,” in Proc. 29th Symp. Operating Syst. Princ. (SOSP), 2023, p. 611–626. [14] H. Jin, S. Li, and M. A. Gregory, “Gensched: Phase-aware generative scheduling for llm inference in heterogeneous edge networks,” in Proc. IEEE Conf. Comput. Commun. (IEEE INFOCOM), 2026, pp. 1–6. [15] Y. Li et al., “Cloud-edge system for scheduling unpredictable llm requests with combinatorial bandit,” IEEE Trans. Serv. Comput., vol. 18, no. 6, pp. 3567–3580, 2025.
6
Avg. End-to-End Latency (s)
LYREO Ly-PPO
Avg. Load-Balancing Deviation (×10−2 )
2.5
Avg. End-to-End Latency (s)
Avg. Load-Balancing Deviation (×10−2 )
13
H = 100 H = 150 H = 200 H = 250 H = 300
5
4
3
2 0
200
400
600
800
1000
1200
Episode
Fig. 8: Impact of truncation length on training performance.
[16] B. Li, Y. Jiang, V. Gadepally, and D. Tiwari, “Llm inference serving: Survey of recent advances and opportunities,” in Proc. IEEE High Perform. Extreme Comput. Conf. (HPEC), 2024, pp. 1–8. [17] X. Zhang et al., “Beyond the cloud: Edge inference for generative large language models in wireless networks,” IEEE Trans. Wireless Commun., vol. 24, no. 1, pp. 643–658, 2025. [18] M. Zhang, X. Shen, J. Cao, Z. Cui, and S. Jiang, “Edgeshard: Efficient llm inference via collaborative edge computing,” IEEE Internet Things J., vol. 12, no. 10, pp. 13 119–13 131, 2025. [19] F. Mou, Z. Tang, W. Jia, and W. Zhao, “Adaptive request scheduling and load balancing for edge deployed large language models,” IEEE Trans. Serv. Comput., vol. 19, no. 2, pp. 934–947, 2026. [20] J. Li, B. Han, S. Li, X. Wang, and J. Li, “Collm: A collaborative llm inference framework for resource-constrained devices,” in Proc. IEEE/CIC Int. Conf. Commun. China (ICCC), 2024, pp. 185–190. [21] B. Zhu, Z. Chen, L. Zhao, H. Shin, and A. Nallanathan, “Enabling efficient large language model inference over wireless networks with caching,” IEEE Trans. Wireless Commun., vol. 25, pp. 18 326–18 343, 2026. [22] A. Younesi et al., “Splitwise: Collaborative edge–cloud inference for llms via lyapunov-assisted drl,” in Proc. IEEE/ACM Int. Conf. Utility Cloud Comput., 2025, pp. 1–11. [23] N. Qiu et al., “Joint request batching and worker assignment in airan edge inference systems,” in Proc. Int. Conf. Future Commun. Netw. (FCN), 2025, pp. 1–6. [24] X. Ma, H. Zhou, T. Wu, and X. Fan, “Preference-aware task routing for edge-cloud hierarchical large language model inference,” in IEEE Conf. Comput. Commun. (IEEE INFOCOM), 2026, pp. 2985–2986. [25] Z. Tang, Y. Sun, W. Chen, J. Ding, and B. Ai, “Gelato: Generative entropy-and lyapunov-based adaptive token offloading for device-edge speculative llm inference,” arXiv preprint arXiv:2605.10124, 2026. [26] Z. Li, C. Yang, X. Huang, W. Zeng, and S. Xie, “Coor: Collaborative task offloading and service caching replacement for vehicular edge computing networks,” IEEE Trans. Veh. Technol., vol. 72, no. 7, pp. 9676–9681, 2023. [27] K. Cheng et al., “Slice-level scheduling for high throughput and load balanced llm serving,” arXiv preprint arXiv:2406.13511, 2024. [28] B. Sun et al., “Llumnix: Dynamic scheduling for large language model serving,” in Proc. 18th USENIX Symp. Oper. Syst. Design Implementation (OSDI), 2024, pp. 173–191. [29] M. Neely, Stochastic network optimization with application to communication and queueing systems. Morgan & Claypool Publishers, 2010. [30] J. A. Arjona-Medina et al., “Rudder: Return decomposition for delayed rewards,” Proc. Adv. Neural Inf. Process. Syst. (NeurIPS), vol. 32, 2019. [31] M. Chen et al., “Ran information-assisted tcp congestion control using deep reinforcement learning with reward redistribution,” IEEE Trans. Commun., vol. 70, no. 1, pp. 215–230, 2021. [32] J. Gui, Z. Li, J. Zhang, X. Deng, and G. Min, “Multi-heterogeneousagent drl for efficient congestion control with reward redistribution in space–air–ground integrated networks,” IEEE Trans. Netw. Sci. Eng., vol. 13, pp. 3035–3052, 2026. [33] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” arXiv preprint arXiv:1707.06347, 2017. [34] L. Zheng et al., “Lmsys-chat-1m: A large-scale real-world llm conversation dataset,” in Proc. Int. Conf. Learn. Representations (ICLR), vol. 2024, 2024, pp. 22 225–22 257.