CS Paper Radar

Minimizing Bottleneck Overload Risk in Online Edge Task Placement under Workload Uncertainty

Lei Wang, Winston K. G. Seah, Gang Xu, Xiaodong Xu, Baoqi Huang

cs.DC ·submitted 2026-11-03 07:14 UTC · v1

Abstract

In edge computing, tasks must be placed on servers of finite capacity before workloads are realized, often with only workload means and variances known. An assignment balanced on expected load can still leave a server with more fluctuations than its residual capacity can absorb. Per-server risk constraints can enforce a prescribed overload tolerance but do not distinguish the assignments that meet it by how close the riskiest server comes to the limit. We show that, for independent tasks, placement preserves a period's total variance and total residual capacity, and decides only how fluctuation, measured by standard deviation, is paired with residual capacity across servers. The risk ratio, the ratio of fluctuation to residual capacity, parameterizes a server's worst-case overload probability over all aggregate workload distributions with given mean and variance. We minimize the largest risk ratio, attained at the risk bottleneck. Risk-Bottleneck Placement (RBP) places tasks in descending order of standard deviation, each on the server with the smallest post-assignment risk ratio, and refines the assignment with relocations and swaps within a finite per-period online budget. On small instances solved exactly by enumerating every assignment, minimizing the maximum expected utilization leaves the largest risk ratio 25.66-29.19% above its exact minimum on average, even with risk-minimizing tie-breaking, and the corresponding gap for RBP is 1.77-2.64%. In trace-derived multi-period simulations at two workload pressures, RBP reduces the worst-server overload probability by 26.0% and 18.0% relative to the best baseline and remains the lowest at every tested pressure and scale.

Comment
15 pages, 2 figures, 7 tables

Closest papers

Nearest neighbours by meaning across the whole index.

PRICE: Pricing-based Resource Incentives for Quality-of-Result-aware Computing at the Edge

cs.DC ·2026-08-21 ·Uwe Gropengießer, Sebastian Frenz, Max Mühlhäuser
published similarity 0.63
Abstract

Edge nodes are capacity-constrained by design, yet many edge workloads can trade result quality for resource efficiency at runtime. Existing edge pricing mechanisms largely treat requests as fixed-configuration submissions and rarely exploit per-request quality flexibility under overload. We present PRICE, an incentive mechanism that couples a utilization-dependent price signal to per-request quality selection. As utilization increases, rising acceptance prices make resource-intensive variants less likely to be selected, shifting accepted requests toward lighter execution and allowing the node to serve significantly more requests while operating near capacity. Evaluation on real hardware under sustained overload shows that PRICE outperforms both fixed-allocation and dynamic-pricing baselines in accepted throughput and CPU utilization. The results are robust across pricing function families, task-duration distributions, and client populations. Result-quality flexibility is a powerful but underused control dimension for overload management at the edge, and pricing is an effective mechanism to exploit it.

0.24

Online Adaptive Computation Reuse in Collaborative Edge Computing: A Two-Timescale Approach

cs.NI ·2026-10-08 ·Xingqiu He, Chaoqun You, Peng Wang, Xiaoyu Liu, Tony Q. S. Quek
benchmark similarity 0.62
Abstract

Collaborative Edge Computing (CEC) is an efficient computing paradigm that enables neighboring edge servers to share computational resources with each other. Although CEC can enhance resource utilization, it still suffers from duplicate computations because nearby end-users often offload tasks with similar inputs. To improve system efficiency, the computation results of previously executed tasks can be cached and reused by subsequent tasks. However, time-varying task popularity and arrival rates require caching and scheduling decisions to adapt to demand changes, while frequent cache updates incur additional costs. To address this issue, this paper develops a two-timescale computation reuse algorithm for CEC networks. We formulate an optimization problem that jointly considers weighted response time and cache update cost, with result caching decisions determined at the frame level and workload scheduling, cache searching, and computational resource allocation adjusted at the slot level. Using recent workload observations, we construct a frame-level surrogate problem and decompose it into a caching subproblem and a scheduling subproblem. For the caching subproblem, we introduce marginal storage efficiency and incorporate cache update costs into a bisectionbased algorithm. Under bounded normalized marginal sensitivity, the algorithm achieves a near-optimal objective value for the single-BS caching subproblem when individual result sizes are small relative to the cache capacity and the relaxed solution is sufficiently accurate. For the scheduling subproblem, we utilize projected gradient descent and backtracking with warm starts across consecutive slots. Numerical results demonstrate consistent performance gains over benchmark schemes across diverse network and workload settings.

0.23

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

cs.AI ·2026-09-15 ·Zhen Li, Jun Cai, Haoran Gao, An Li, Tan Li
similarity 0.62
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.

0.17

Stochastic AI Model Placement for AI-and-RAN Coexistence in 6G Networks

cs.NI ·2026-11-05 ·Alaa M. Altarazi, Mohammad J. Abdel-Rahman
hot direction similarity 0.61
Abstract

This paper considers AI-service placement over geographically distributed RAN sites equipped with GPU resources partitioned into fixed, isolated multi-instance GPU (MIG) profiles. We propose C$^2$AIR, a chance-constrained optimization model that maximizes expected AI requests served while protecting uncertain RAN workloads and enforcing probabilistic capacity reliability requirements for admitted AI services. C$^2$AIR allows a service to run at multiple sites and accounts for discrete profile, memory, and GPU-slice constraints. We evaluate C$^2$AIR on a four-site deployment calibrated from NVIDIA Aerial RAN capacity figures and MLPerf Inference results, and on seven larger scenarios with up to 15 sites and 40 AI services, computing every violation and overload probability exactly from the demand distributions. C$^2$AIR keeps the RAN violation probability within its target at every hour of the day, whereas reserving for the mean RAN demand violates it in 24\% to 47\% of the intervals. The reliability condition prevents placing AI models that would be overloaded in 85\% of the intervals at an event hour, and multi-site replication serves 2.7 times more AI requests than single-site deployment. The evaluation also shows that coarse MIG instances and a heavy demand tail can make strict RAN protection expensive.

0.35

Robustness Starts with the Objective: Designing and Certifying Robust LLM-Generated Heuristics

cs.AI cs.CLcs.DCcs.PF ·2026-10-31 ·Pantea Karimi, Roozbeh Bostandoost, Dany Rouhana, Siva Kesava Reddy Kakarla, Pooria Namyar +3 more
similarity 0.60
Abstract

LLMs are increasingly used to design heuristics for computer systems. However, most synthesis frameworks evaluate candidates by their average performance, which can mask severe regressions on specific workloads. Even adding adversarial training inputs doesn't eliminate these regressions, and percentile objectives (e.g., optimizing for the 95th percentile) overlook how severe regressions can be beyond the selected threshold. We present TAILOR, a framework that guides LLM synthesis using the Conditional Value at Risk (CVaR) of the cost difference between each candidate and an existing baseline on the same workload. This paired CVaR measures the average difference over the worst fraction of workloads. We show that a negative paired CVaR guarantees improvements in both average performance and tail optimality gap relative to the unknown optimum, without ever computing that optimum. We find that TAILOR achieves the best mean--tail trade-off among the synthesis objectives we evaluate across three case studies: Azure GPU batch admission, Azure VM packing, and server placement. Tested across seven diverse optimization benchmarks, TAILOR produces heuristics that are certified with 99% confidence to improve both average performance and tail optimality gaps over the baseline in six of them. On these six benchmarks, TAILOR also outperforms known robust, human-designed alternatives in the tail while achieving better or comparable average-performance improvement over the baseline.

0.31

Prediction-Robust Service Deployment with Capacity-Aware Edge Admission

cs.DC ·2026-09-01 ·Hailiang Zhao, Ziqi Wang, Yifei Zhang, Mingyi Liu, Xinkui Zhao +2 more
theory similarity 0.60
Abstract

Edge platforms instantiate executable services close to users to reduce request-serving cost, but each instance incurs a one-time deployment cost and remains useful only for a finite time-to-live (TTL). The resulting online decision is both prediction-sensitive and capacity-coupled: an optimistic forecast can waste deployment cost, whereas a delayed decision misses the burst it is intended to serve. We study this problem under a common TTL cost model and propose CAPSUM, a capacity-aware admission policy with an elastic specialization, CAPSUM-E. In the local elastic setting, every node-service trace is exactly a variable-price Bahncard instance. This reduction lets CAPSUM-E inherit PFSUM's tight prediction-error-dependent ratio, including $2/(1+β)$ consistency and $1/β$ robustness for $β>0$. A redirect-aware variant preserves the same local deployment schedule. For finite-capacity nodes, CAPSUM combines size-scaled break-even tests, a utilization-dependent shadow price, and evidence-density eviction; we prove capacity feasibility, scale invariance, and exact agreement with CAPSUM-E under an elastic configuration. We implement an exact local offline dynamic program and compare against direct common-model baselines and documented source-derived adapters for EDP-A, OREO, and uEDC-L. Experiments cover controlled prediction error, three synthetic demand regimes, a causal predictor on a public Globus Compute trace, and joint scaling to 1,024 nodes and 10,000 services. Under the common model, CAPSUM reduces normalized cost by 33.7-42.9% relative to the best source-derived adapter across the synthetic regimes and by 45.5% on the sampled trace.

0.27

On the Impact of Degradation-Balanced Scheduling in Manycore Systems

cs.AR ·2026-10-06 ·Maria Pantazi-Kypraiou, George Goudroumanis, George Floros, Anuj Pathania, George Stamoulis
publishedunusual similarity 0.60
Abstract · Accepted at ICECS 2026

Electromigration degradation in manycore systems depends strongly on how runtime workload is distributed across cores. Task placement affects power, temperature, and current density, which in turn shape the spatial distribution of degradation over time. However, a scheduler that ranks cores only by their current reliability state may not always distinguish among candidate cores, especially when reliability values are close at decision time. In this case, scheduling decisions can be driven by secondary factors rather than by long-term degradation balance. This paper studies degradation-balanced scheduling and proposes a Reliability-Balanced (RB) policy that predicts the full-task effect of each candidate assignment. RB penalizes added imbalance in electromigration exposure, stress, active time, and task count while guarding the predicted Rvalue floor. On randomized continuous mixed workloads, the proposed scheduler preserves completed tasks while improving average Rvalue by 0.37% and minimum Rvalue by 4.35%. It reduces Rvalue, exposure, stress, and active-time standard deviation by 10.84%, 9.39%, 8.35%, and 16.38%, respectively.

0.35

Spot Markets for AI Inference: Dynamic Capacity Allocation and Pricing on a Shared Accelerator Fleet

eess.SY ·2026-11-08 ·Quanyan Zhu
similarity 0.60
Abstract · 39 pages, 12 figures, 4 tables

Inference providers size their accelerator fleets for the interactive peak and sell spare capacity through fixed discounts, such as batch tiers at half price. However, inference differs from conventional cloud capacity in four respects: capacity depends on the latency tier through batching, moving weights between models is slow and costly, spot demand can wait until its deadline, and power can bind. In this paper, we develop a framework for dynamic capacity allocation and pricing of AI inference on a shared accelerator fleet. We consider a provider that serves several models under a power cap and sells each model in an interactive tier with a speed promise and in a spot tier for preemptible work with a deadline. In each period, the provider chooses how many replicas of each model to keep loaded and what spot price to quote. We show that one interactive token displaces a fixed number $ρ_m>1$ of spot tokens, and that the optimal spot price lies midway between the interactive price and the effective cost of capacity in the deadline window, which is close to the prevailing half price only when the fleet is slack. We further show that a spot tier raises the optimal reliability of the interactive tier, and that placement should follow persistent demand shifts while prices absorb transients. Building on these results, we design a model predictive controller based on a linear program with explicit approximation bounds, which solves each period in milliseconds. Numerical experiments on a simulated week with a measured daily demand profile, a flash crowd, and a grid curtailment show that the controller raises profit by 7.4% over fixed half-price practice, captures 93% of the gain available with perfect forecasts, keeps the interactive promise through both events, and leaves spot buyers better off.

0.28