CS Paper Radar

Joint Service Depth and Priority Design in Queueing Systems

Adam N. Elmachtoub, Yash Kanoria, Jonathan Y. Tan

cs.GT econ.THmath.OC ·submitted 2026-10-23 22:10 UTC · v1

Abstract

In AI-assisted service systems, the server can choose how much processing effort to spend on each job, which we call the service depth. Deeper reasoning improves output quality but occupies the server longer and increases congestion, and the realized processing time remains random because AI models are probabilistic and tasks vary in complexity. We study the joint design of service depth and priority in a single-server queue whose customers differ in delay sensitivity, with the goal of maximizing social welfare. For each customer type, the decision maker chooses a priority level and a service depth, and service times are exponential with mean equal to the chosen depth. With two customer types and linear service values, we characterize the centralized optimum. Counterintuitively, it prioritizes the patient type and gives it a smaller service depth when patient customers are sufficiently prevalent. When delay sensitivity is private, however, incentive compatibility requires the impatient type to receive a weakly shorter sojourn time, so the optimal price menu never prioritizes the patient type. Consequently, there can be a welfare gap between the centralized decision maker's optimal control policy and the optimal decentralized pricing mechanism. With a continuum of types, the centralized optimum is monotone: more delay-sensitive customers receive weakly smaller depth and higher priority, so the optimum can be implemented by a price menu with no welfare loss. Allowing randomized depths similarly closes the gap in the two-type model. Finally, we calibrate an agentic AI service system using published coding-agent trials from DeepSWE and numerically examine priority inversion, the value of joint design, and the welfare gain from personalization.

Closest papers

Nearest neighbours by meaning across the whole index.

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

eess.SY ·2026-11-08 ·Quanyan Zhu
similarity 0.63
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

List Update with Per-Page Maximum Delay

cs.DS ·2026-11-10 ·Tianhang Lu, Runtian Ren, Shengcai Liu
similarity 0.60
Abstract

We study list update with per-page maximum delay. Requests may wait, and one access clears all pending requests of a page at its current list rank, paying their maximum waiting penalty. Each service can change the permutation and therefore the cost of later accesses. We give a strictly $5$-competitive deterministic algorithm: serve a page when the oldest waiting time reaches two thirds of its current rank, then move it to the front. Our main tool is an asynchronous marked-rank coupling that compares different list orders and different service histories. A temporal transfer principle separates this permutation argument from two waiting-cost inequalities. It gives factor $5$ for page-specific superadditive penalties, common calendar rates, and additional hard deadlines; deadlines alone admit factor $3$. Two structural conditions on request-specific penalties give factor $3+2κ$. In particular, nonincreasing request severity retains factor $5$ even with unbounded weight ratios. For linear delay, offline optimization is NP-complete but fixed-parameter tractable in the number of pages. We characterize fixed-list batching, show an $Ω(m)$ gap between the best static order and dynamic reordering, and prove that the optimal deterministic factor for one page is exactly $2$. Counterexamples delineate the threshold rule's scope.

0.20

User Satisfaction-Aware Resource Allocation with Prospect-Theoretic Utility for Multimedia Streaming

cs.NI ·2026-08-11 ·Manoj Kumar S, Pranjal Varshney, Avhishek Chatterjee
similarity 0.60
Abstract

Traditional resource allocation policies for multimedia streaming have primarily targeted metrics such as throughput, fairness and delay. However, user satisfaction is known to be strongly influenced by variations in throughput. Although some recent works have considered throughput variations, they overlooked a well-known aspect of human behavior that has reshaped behavioral economics over the past few decades: the same amount of decrease in throughput causes greater annoyance than the satisfaction caused by the increase. Motivated by this insight from the broad field of economics, popularly known as prospect theory, we propose a generic utility (metric) that captures both the average throughput and the asymmetric effect of throughput variations on user satisfaction. Next, we propose a resource allocation policy that reduces abrupt decreases in allocated resources when the system transitions from a resource-rich to resource-scarce state while respecting the priorities of different classes of users. Extensive simulations show that this policy outperforms the existing fair allocation policies. However, the choice of the optimal threshold depends on the network instance, which, in practice, may change frequently. Hence, building on the theoretical analysis of multi-queue systems, we propose fast numerical methods for determining the optimal threshold, which can be used in field deployments.

0.04

Optimal Scheduling in Generalized Switch in Heavy Traffic

cs.PF ·2026-09-15 ·Runhan Xie, Ziv Scully, Rhonda Righter, Izzy Grosof
theory similarity 0.59
Abstract

The generalized switch is a highly flexible queueing model, covering multiclass, multiserver, and multiresource queueing systems as well as a wide variety of stochastic networks. Although many scheduling policies have been developed for this model, they almost entirely address unknown job duration settings. How to optimally use known job durations in the generalized switch has remained open. Moreover, optimizing mean response time remains open in both settings. We introduce the first policy to guarantee heavy-traffic optimal mean response time in the generalized switch, our Smallest Equalizing Bucket (SEB) policy. The key challenge in designing an optimal scheduling policy is that we must simultaneously prioritize small jobs and also minimize resource waste, all while fitting within the generalized switch's service options. SEB overcomes this challenge by grouping jobs into duration-based buckets and enforcing an "equalizing" service structure that keeps each bucket balanced while still prioritizing the smallest jobs. We prove SEB's heavy-traffic optimality. Simulations further confirm the effectiveness of SEB-inspired heuristics.

0.28

Stochastic Aggregation with Prescribed Resources and Additive Delay

cs.DS ·2026-11-10 ·Tianhang Lu, Runtian Ren, Shengcai Liu
similarity 0.58
Abstract

We study online aggregation with prescribed resources and additive delay. In this problem, we are given a finite set of resources with purchase costs and a collection of request types, each specifying the resources it requires. Requests arrive over time, and each request can be served immediately or postponed to a later time. A service may serve several pending requests together by purchasing every resource required by at least one of them, paying for each purchased resource only once. These purchases serve only the current batch; resources needed in a later service must be purchased again. A request served $t$ units of time after its arrival incurs delay cost $t$. The objective is to serve all requests while minimizing the sum of resource purchase costs and individual delay costs. We consider a stochastic version of this problem in which requests of each type follow an independent Poisson process of known rate. An online algorithm knows these rates but observes requests only upon arrival. We compare its expected cost with that of an offline optimum that knows the entire realized input and may choose every batch freely. A resource--scale linear program supplies both an offline lower certificate and synchronized service periods. This yields a deterministic online algorithm with polynomial-time preprocessing on rational input and a long-run ratio of expectations below $2.113$. The guarantee applies in particular to rooted multi-level aggregation and prescribed-pair aggregation on trees. Besides, for Poisson TCP acknowledgment, we further characterize the optimal long-run ratio of expectations at every load, showing that its worst-case value is approximately 1.409 and is attained by a deterministic online policy.

0.17

Whittle index approach to multi-server scheduling with convex delay costs and impatient customers

cs.PF math.PR ·2026-09-17 ·Samuli Aalto
similarity 0.58
Abstract

We consider the dynamic scheduling problem in a multi-class M/G/N + M queue with convex delay costs and impatient customers that have exponential abandonment times. We apply the Whittle index approach to find a reasonable heuristic solution for this tricky problem. By assuming exponential abandonment times, we are able to make a very straightforward use of the results of the corresponding problem with patient customers presented in Queueing Systems, Vol. 110, Article no. 2, 2026. Our main theoretical achievements are proving that the closed version of the corresponding discrete-time problem is indexable and deriving an explicit expression for the Whittle index. The discrete-time results are utilized to develop the Whittle index policy for the original continuous-time scheduling problem.

0.24

Online Covering with Maximum Delay under Subadditive Service Costs

cs.DS ·2026-09-26 ·Tianhang Lu, Runtian Ren, Shengcai Liu
theory similarity 0.58
Abstract · 23 pages, 4 figures

We study online covering in which each instantaneous service pays its purchase cost and one maximum waiting time, with no effect on future requests. For static realizable services, monotone subadditivity suffices for optimal competitive ratios; submodularity is unnecessary. A normalized monotone subadditive lower-bound oracle with realization factor $ρ$ yields ratios $ρ+1$ deterministically and $1/(1-e^{-1/ρ})$ randomly against an oblivious adversary. Exact batch optimization gives the optimal constants $2$ and $e/(e-1)$. The randomized algorithm uses one global threshold on a seed-independent virtual-height trajectory, whose active time is a lower bound on the offline optimum. Weighted vertex cover gives a strict separation from submodularity on a three-edge bipartite path, with polynomial-time batch implementations through min-cut and LP rounding. An offline consecutive-batch normal form also transfers static approximation guarantees to the offline problem.

0.09

Online Service with Per-Batch Maximum Delays

cs.DS ·2026-08-19 ·Tianhang Lu, Runtian Ren, Shengcai Liu, Ke Tang
similarity 0.58
Abstract

We study online service with per-batch maximum delays on a finite metric space. Requests arrive over time, and a server serves each batch by following a walk visiting its requests' locations. Movement is instantaneous. The objective is to minimize the total distance traveled by the server plus the sum, over all batches, of the maximum waiting time in each batch. We give deterministic polynomial-time algorithms with competitive ratios $10$ on finite lines, $12$ on weighted trees, and $20$ on arbitrary finite metrics. Unlike additive delay, maximum delay allows younger requests to join a batch without increasing its delay charge. Our algorithms coordinate service using a common waiting clock and a threshold determined by the metric. The analysis uses certificates for groups of requests to compare this policy with any offline schedule, even one that serves different batches and follows different walks. This comparison shows that coordinating service in this way loses only a constant factor. The bounds hold whether the server must serve requests it visits or may leave them unserved; the two rules also have equal offline optimal costs. Offline optimization is polynomial on lines and explicitly represented weighted trees, and NP hard on general metrics. When arrivals are announced but locations are hidden until visited, we give an $84$-competitive algorithm on a known finite line under either rule.

0.13