PaperlayerView exact revision on arXiv

Source-linked AI summary

End-to-End Latency-Minimizing and Load-Balanced Request Scheduling for Edge LLM Inference in Agentic AI Services

Zhen Li, Jun Cai, Haoran Gao, An Li, Tan Li

arXiv:2609.17193v1cs.AI

TL;DR

Edge LLM scheduling must account for heterogeneous servers, evolving inference states, and latency outcomes delayed until request completion. The paper models these cross-slot processes and proposes LYREO, which combines Lyapunov optimization with reward redistribution. Simulations report lower latency and more balanced load than existing baselines.

  • Problem

    Conventional latency models do not capture fine-grained multi-stage LLM execution, and scheduling outcomes arrive only when requests complete.

    Source: §I · p. 1

  • Method

    The paper models cross-slot inference and KV-cache workload, then uses Lyapunov optimization and reward redistribution in its LYREO scheduling approach.

    Source: §I · p. 2

  • Results

    LYREO consistently reduces end-to-end latency and load-balancing deviation, outperforming existing baselines in extensive evaluations.

    Source: §VI · p. 13

  • Takeaways & Limitations

    The reported evaluations support LYREO's joint treatment of end-to-end latency and load-balancing deviation in edge LLM scheduling.

    Source: §VI · pp. 12–13

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper frames edge LLM scheduling as a cross-slot problem involving multi-stage inference, delayed outcomes, and workload imbalance. It introduces LYREO and a fine-grained inference model to address these challenges.

I. INTRODUCTION

  • LYREO combines Lyapunov-guided long-term load balancing with reward redistribution to address delayed feedback in online scheduling.Sequence truncation and value bootstrapping support return estimation in the infinite-horizon setting.Source: §I · p. 2
  • The model tracks transmission, batching, prefill, iteration-level decoding, and KV cache evolution as unfinished requests interact across slots.The resulting formulation minimizes long-term end-to-end latency subject to peak-memory feasibility and long-term load balancing.Source: §I · p. 2
  • Normalized KV cache memory-time consumption characterizes server workload by accounting for memory use over time.The metric supports a long-term load-balancing constraint alongside latency minimization and peak-memory feasibility.Source: §I · p. 2
  • LYREO consistently reduces end-to-end latency and load-balancing deviation, outperforming existing baselines in extensive evaluations.The introduction reports evaluations across diverse system and algorithm configurations.Source: §I · p. 2

II. RELATED WORK

  • Prior work covers inference-engine techniques and edge scheduling, but often simplifies requests as atomic tasks or leaves long-term heterogeneous load balancing underexplored.The paper identifies delayed-outcome attribution as an open issue in prior DRL and Lyapunov-based scheduling studies.Source: §II · pp. 2–3

A. System Overview

  • The system has a scheduler, mobile users, and edge servers; each user generates a request at each slot, and servers may still process earlier requests.The scheduler assigns requests using collected metadata while prior requests remain in service.Source: A. System Overview · p. 3

B. Communication Model

The communication and inference models represent request service as a multi-stage process. Batched prefill and dynamic decoding share edge-server resources while requests can remain active across slots.

B. Communication Model

  • Users transmit request tokens to assigned edge servers, where each server's bandwidth is shared among its scheduled requests.The transmission rate depends on channel conditions and the number of requests scheduled to that server.Source: B. Communication Model · p. 3

C. LLM Inference Model

  • LLM serving is modeled with separate prefill and autoregressive decoding phases, rather than static batching with single-slot completion.The serving model incorporates continuous batching and iteration-level dynamics.Source: C. LLM Inference Model · p. 4

1) Prefill Phase:

  • Batched prefill processes the slot's arriving prompts together to compute first output tokens and generate their KV caches.The model treats prefill as compute-bound and independent of decoding when sufficient KV-cache memory is available.Source: 1) Prefill Phase · p. 4

2) Decoding Phase:

  • Decoding generates one token per iteration; dynamic entry-and-exit decoding admits new requests and evicts completed ones as KV-cache capacity permits.Requests may remain unfinished across slots, while their cache use and active batch membership change during decoding.Source: 2) Decoding Phase · pp. 4–5

D. Memory Analysis

The paper treats KV-cache occupation as both a feasibility constraint and a measure of ongoing server workload. Its normalized memory-time metric captures the pressure of cache use across heterogeneous servers.

D. Memory Analysis

  • KV-cache occupation is a stateful resource that affects decoding throughput and serving capacity, so the model tracks it throughout inference.Peak occupation must remain within each server's reserved KV-cache memory capacity.Source: D. Memory Analysis · p. 5
  • Peak-memory feasibility also acts as an admission condition, ensuring enough GPU memory for prefill and avoiding additional engine-level waiting after batching.The same constraint prevents cache overflow as decoding generates tokens.Source: D. Memory Analysis · p. 5
  • Normalized KV-cache memory-time consumption measures cumulative cache residency relative to a server's available memory-time capacity.Normalization reflects memory scarcity, while duration-weighting gives greater workload contribution to slower decoding iterations.Source: D. Memory Analysis · p. 5

E. Problem Formulation

The formulation minimizes long-term average end-to-end latency while enforcing memory feasibility and long-term load balance. Its decisions are difficult to evaluate immediately because request latency depends on evolving system state and becomes observable only at completion.

E. Problem Formulation

  • The formulation constrains workload deviation across servers over the long term and limits KV-cache occupation to available memory.Scheduling variables are binary and each request is assigned to one server.Source: E. Problem Formulation · p. 6
  • The objective minimizes long-term average request latency, including transmission, batch waiting, prefill, and decoding.The scheduling decision assigns each arriving request to an edge server in each slot.Source: E. Problem Formulation · pp. 5–6
  • Scheduling is temporally coupled because a request's latency depends on past decisions and future system evolution, and is observed only after completion.Unknown request attributes, user locations, channel conditions, and heterogeneous server throughputs add to the optimization difficulty.Source: E. Problem Formulation · p. 6

IV. LYREO APPROACH

LYREO treats P1 as a sequential decision-making problem, using Lyapunov optimization for long-term load balancing and reward redistribution to attribute delayed latency feedback to decisions.

  • LYREO treats P1 as a sequential decision-making problem that jointly addresses the identified challenges.Source: §IV · p. 6
  • Lyapunov optimization reformulates P1 to handle its long-term load-balancing constraint.Source: §IV · p. 6
  • Reward redistribution attributes delayed latency feedback to its associated decisions before policy optimization.Source: §IV · p. 6

A. Problem Reformulation via Lyapunov Optimization

The reformulation tracks accumulated server workload deviation with virtual queues, then converts the long-term load-balancing constraint into a per-slot corrective term; future-dependent latency still makes the resulting problem intractable.

  • Virtual queues track each server’s accumulated workload deviation so scheduling decisions can account for the horizon-wide load-balancing constraint.The constraint couples decisions across the entire horizon and cannot be evaluated from one slot alone.Source: A. Problem Reformulation via Lyapunov… · p. 6
  • Queue stability implies that long-term workload deviation does not exceed threshold ϵ, satisfying the load-balancing constraint.Each queue tracks cumulative excess of instantaneous deviation Ys(t) over ϵ.Source: A. Problem Reformulation via Lyapunov… · p. 6
  • The quadratic Lyapunov function measures virtual-queue backlog, and its drift-plus-penalty objective balances latency minimization against long-term load balance using control parameter ν.A smaller Lyapunov value indicates that the long-term constraint is well satisfied.Source: A. Problem Reformulation via Lyapunov… · pp. 6–7
  • The per-slot reformulation remains intractable because latency depends on future information and is observed only after inference completion.Subsequent requests assigned to the same server also influence the resulting end-to-end latency.Source: A. Problem Reformulation via Lyapunov… · p. 7

B. Delayed-Feedback-Aware Policy Learning

The policy-learning framework represents scheduling as a sequence decision process and redistributes delayed returns into decision-level signals, using truncated and bootstrapped return prediction for the infinite-horizon setting.

1) Sequence-Markov Decision Process Formulation:

  • The sequence-Markov decision process represents scheduling as state-action transitions with rewards that need not satisfy the Markov property.Source: 1) Sequence-Markov Decision Process… · p. 7
  • At each slot, the scheduler observes system information and assigns every incoming request to an edge server; the state includes server capabilities and dynamic status.The reward combines total latency, virtual-queue load-balancing deviation, and a GPU-memory feasibility penalty.Source: 1) Sequence-Markov Decision Process… · p. 7

2) Reward Redistribution:

  • Reward redistribution reallocates the sequence’s total return across state-action pairs while preserving cumulative return and the optimal policy.Source: 2) Reward Redistribution · p. 7
  • The redistributed reward assigns each state-action pair the increment in expected return, providing a step-wise learning signal that removes reward delay in expectation.A pair that increases cumulative return receives a positive redistributed reward even if the original delayed reward has not yet reflected that improvement.Source: 2) Reward Redistribution · p. 8
  • For infinite-horizon return prediction, LYREO combines observed rewards through truncation point H with a bootstrapped estimate of the remaining discounted return.An LSTM predicts returns conditioned on variable-length state-action sequences and is trained against this truncated-bootstrapped target.Source: 2) Reward Redistribution · p. 8

3) Scheduling Policy Optimization:

LYREO optimizes its scheduling policy with PPO actor and critic networks using redistributed rewards; its analysis bounds policy performance under stated reward, estimation, and optimization assumptions.

3) Scheduling Policy Optimization:

  • PPO optimizes actor and critic networks using the immediate signals from redistributed rewards, without requiring an explicit system transition model.The actor’s clipped surrogate objective constrains policy updates; generalized advantage estimation supplies the advantage function.Source: 3) Scheduling Policy Optimization · p. 8

C. Algorithm Summary and Theoretical Analysis

  • Theorem 1 bounds LYREO’s learned-policy performance gap under bounded rewards and stated critic, return-prediction, and PPO optimization errors.The analysis attributes the gap to approximating ideal redistributed signals through sequence truncation and value bootstrapping.Source: C. Algorithm Summary and Theoretical… · pp. 8–9

A. Simulation Settings

The simulations use Llama-3.2-1B on three heterogeneous NVIDIA GPU platforms, with profiled prefill and decoding rates. Requests come from LMSYS-Chat-1M, and training and evaluation use specified inference and time-slot settings.

  • Each edge server runs Llama-3.2-1B on an RTX 3080, RTX 3090, or RTX 4090 GPU.Source: A. Simulation Settings · p. 9
  • Across the corresponding GPU platforms, available memory capacities are 10, 20, and 24 GB, while profiled prefill rates are 2500, 4000, and 8000 tokens/s, respectively.Decoding throughput is obtained via offline profiling of Llama-3.2 using a vLLM-based serving engine on the corresponding GPU platforms.Source: A. Simulation Settings · p. 10
  • Requests use LMSYS-Chat-1M, with average input and output lengths of 70 and 215 tokens; each token uses 16 KB of KV cache and transmits 16 bits.The simulation runs for 800 one-second slots with load-balancing tolerance 0.01; user locations vary within a 200 × 200 m² service area.Source: A. Simulation Settings · p. 10
  • Training uses only the currently observed trajectory, and unfinished requests continue after the final slot with rewards assigned to the final step.The return predictor is a two-layer LSTM with hidden dimension 64.Source: A. Simulation Settings · p. 10

B. Baseline Approaches

LYREO is compared with learning-based and heuristic schedulers. It has the strongest reported convergence and evaluation-run distributions for latency and load balancing, while Lyapunov-guided approaches outperform fixed-penalty PPO on balancing.

B. Baseline Approaches

  • The baselines include Ly-PPO without reward redistribution, PPO with a fixed penalty, Static batching, Least-Loaded scheduling, and random server selection.Source: B. Baseline Approaches · p. 10

1) Convergence Performance:

  • LYREO converges to about 2.4 s average end-to-end latency and 0.02 average load-balancing queue length, versus Ly-PPO’s 3.9 s and 0.09 and PPO’s 5.2 s and 0.22.Source: Figure 2 · p. 10, 1) Convergence Performance · p. 10
  • Reward redistribution gives LYREO more informative temporal feedback, while Lyapunov virtual queues provide adaptive balancing signals tied to accumulated deviation.The paper attributes LYREO’s improvement over Ly-PPO to reward redistribution and the gap between PPO and Lyapunov-guided approaches to adaptive queue-based correction.Source: 1) Convergence Performance · p. 10

2) Distribution Comparison:

  • Across evaluation runs, LYREO has the lowest median end-to-end latency and most compact distribution; LYREO and Ly-PPO have lower load-balancing deviations than the other baselines.Source: 2) Distribution Comparison · p. 10, Figure 3 · p. 11
  • PPO outperforms most non-learning baselines on both metrics, while Static has lower latency than LL, LL balances better, and Random performs worst on both.Source: 2) Distribution Comparison · p. 11

D. Load-Balancing Ablation

The ablation shows that latency-only scheduling trades lower average latency for worse workload balance and tail latency, while KV cache memory-time consumption outperforms active-request counts. System-parameter and hyperparameter evaluations show LYREO’s performance across server scales and heterogeneity, alongside a latency–balance trade-off as ν changes.

D. Load-Balancing Ablation

  • LYREO-NoLB lowers average latency but raises deviation 125.0%, high-KV ratio to 14.35% (123.5% higher), and P99 latency to 6.73 s (79.9% higher) versus LYREO.LYREO-Count reaches 2.79 s average latency, 4.56 s P99 latency, 0.011 average deviation, and an 8.04% high-KV ratio, underperforming LYREO on all four metrics.Source: D. Load-Balancing Ablation · p. 11, Table II · p. 11

1) Impact of System Parameters:

  • Across tested user and server scales, LYREO achieves the best latency and load-balancing deviation; its latency reduction versus Ly-PPO averages roughly 33% as users increase.With more servers, latency falls for all methods, while deviation has no clear monotonic trend; LYREO remains lowest across settings.Source: 1) Impact of System Parameters · pp. 11–12, Figure 4 · p. 12, Figure 5 · p. 12

E. Hyperparameter Sensitivity

  • Increasing ν from 0.05 to 2 lowers latency from about 5.6 s to 2.1 s while load-balancing deviation rises, especially beyond ν = 0.5.Longer return-predictor truncation H lowers final latency, but gains become marginal beyond H = 250; H = 300 also shows larger fluctuations than H = 250.Source: E. Hyperparameter Sensitivity · p. 12, Figure 7 · p. 13

1) Impact of System Parameters:

  • Average load-balancing deviation rises from homogeneous to moderate and heterogeneous hardware for every method, while LYREO remains lowest and slightly outperforms Ly-PPO.The tested configurations use 8× RTX 3090 GPUs; 3× RTX 3080, 3× RTX 3090, and 2× RTX 4090 GPUs; and 4× RTX 3080, 1× RTX 3090, and 3× RTX 4090 GPUs.Source: 1) Impact of System Parameters · p. 12, Figure 6 · p. 13

VI. CONCLUSION

  • LYREO consistently reduces end-to-end latency and load-balancing deviation, outperforming existing baselines.Its model captures transmission, multi-stage inference, and KV cache evolution, and its method redistributes delayed outcomes to responsible decisions.Source: §VI · pp. 12–13

Related papers

Loading 2609.17193v1…