CS Paper Radar

Critical heavy traffic and diffusion limits for shortest-of-d dynamic routing

Elmira Yu. Kalimulina

cs.PF math.PR ·submitted 2026-11-17 10:56 UTC · v1

Abstract

We study shortest-of-$d$ routing, with fixed $d\ge2$, in $N$ parallel queues with independent finite-state Markov service environments switching at rate $κ_N$. At the critical load $ρ_N=1-1/N$, the empirical measure of the centered queue lengths, under stationarity, converges in distribution to a random probability measure determined by its mean. We identify the mean's density and the conditional independence of fixed finite collections of centered queues in the limit. On time scales of order $N$, the centered empirical mean converges to a diffusion with explicit drift and constant diffusion coefficient. These limits hold when $κ_N/N\to\infty$, along subsequences with convergent lattice phase. The diffusion limit extends to centered initial empirical measures tight in the first Wasserstein topology, with means converging in law. A short initial layer prepares the limiting family while preserving the limiting mean. Empirical approximation holds in time-integrated Wasserstein distance.

Closest papers

Nearest neighbours by meaning across the whole index.

Approaching Optimal Scaling of Queue Size for an Input-Queued Switch

cs.PF math.PR ·2026-10-27 ·Taha Ameen, Weina Wang
similarity 0.60
Abstract

We study the scaling of the expected total queue length in an $n\times n$ input-queued switch. It has been conjectured that the optimal scaling is $O(n/(1-ρ))$, up to logarithmic factors, where $ρ$ is the system load. This conjecture has been established in the traditional heavy-traffic regime and in certain sub-regimes of the large-system regime. But it remains unresolved over a wide range of load scalings in the large-system regime. In this paper, we develop a family of scheduling policies parameterized by a positive integer $k\ge 2$. We show that under uniform traffic, our policy achieves an expected total queue length of $O\bigl({n\log\max\{n,1/(1-ρ)\}}\big/{(1-ρ)^{2^k/(2^k-1)}}\bigr)$, as long as $ρ\to 1$ in the large-system regime. As $k$ increases, the exponent $2^k/(2^k-1)$ approaches $1$, bringing our bound arbitrarily close to the conjectured scaling. The expected amortized scheduling cost of the policy is $O(n^3 k)$ per time slot. Our policy is of a batching type, with a novel recursive design that allows an arbitrary number of batching levels. This design principle may also be useful for other scheduling problems in which combinatorial constraints restrict which jobs can be served simultaneously.

0.20

Tandem Queues with Hybrid Abandonment in Heavy Traffic

cs.PF math.PR ·2026-10-08 ·Cameron Curtis, Izzy Grosof, Seyed Iravani
theory similarity 0.59
Abstract

Hybrid-abandonment systems, where jobs abandon from certain stages of service but not others, occur frequently in medical, service, and computing systems. Abandonment affects the heavy-traffic behavior of both the stages with and without abandonment. In contrast to existing heavy-traffic works that focus on cases where there is abandonment at either all stages or no stages, we focus on the heavy-traffic behavior for these hybrid-abandonment systems. We provide the first heavy-traffic characterization of the second queue length in a two-stage tandem queue with abandonment only in the first stage. We characterize the scaled mean of the second stage queue length and prove that the scaled second queue length is asymptotically exponentially distributed and asymptotically independent of the first stage queue length. We derive our results by analyzing Markovian arrival process queues with countably infinite phases. We do this by extending techniques used to analyze queues with Markov-modulated arrivals to the broader class of infinite Markovian arrival process queues. We prove asymptotic results for a more general infinite phase process condition, an infinite birth-death phase process, and the hybrid-abandonment tandem case. We also empirically demonstrate that our heavy-traffic approximations are good approximations across various system settings.

0.25

Diffusion Removes Langevin's Conditioning Dependence: A Sharp Gaussian Analysis

cs.LG stat.ML ·2026-10-08 ·Adam Perbost, Francis Bach, Pierre Marion
hot direction similarity 0.58
Abstract · 49 pages (10 main + appendix), 3 figures

Despite their empirical success, why diffusion models overcome the bottlenecks of classical score-based samplers remains unclear. In this work, we leverage Gaussian distributions to isolate this phenomenon. We establish 2-Wasserstein convergence bounds for optimized hyperparameters, showing that diffusion processes achieve a sampling error of $O(\sqrt{dλ_{\max}}\log N/N)$, where $d$ is the dimension, $N$ the number of sampling steps, and $λ_{\max}$ the largest eigenvalue of the target covariance matrix. Unadjusted and underdamped Langevin dynamics suffer from an additional $\sqrtκ$ factor, where $κ$ is the condition number. These rates follow from spectral bounds which are sharp: we confirm them via matching first-order asymptotics as $N\rightarrow\infty$. Our analysis provides a rigorous characterization, in the Gaussian setting, of how time-dependent score trajectories remove condition-number dependence during sampling. By contrast, in the learning phase, we show that estimating the unnoised score by gradient descent leads to essentially the same estimator as estimating a noisy score, which suggests that the benefits of noising do not come from the learning phase.

0.35

Local decisions, diffusive influence, and lower bounds for graphical balanced allocation

cs.DS math.PR ·2026-09-30 ·Obinna Okechukwu
theorycode/data similarity 0.58
Abstract · 28 pages, 2 figures. All numbered results are formalized in Lean 4: https://github.com/obinnaokechukwu/cycle-gap-lowerbound-lean

In graphical two-choice allocation, each arriving ball is assigned to one endpoint of a random edge. We study rules whose decision is a monotone function of the two endpoint loads, allowing edge-dependent thresholds and fresh randomization. Such a rule has an exact unit-discrepancy coupling: adding one ball to the initial state produces one tagged discrepancy at every later time. We represent the tag by conditional-expectation projections on the marked edge space and obtain diffusive displacement bounds. A transport-volume inequality then converts slow propagation of influence into lower bounds for the load gap. On the cycle with $n$ vertices, from every initial distribution and at every physical time $t\ge 1/n$, the expected gap is at least a constant times $\min\{\sqrt n,t^{1/4}\}$, and the gap exceeds this scale with probability at least $1/8$. After exactly $k\ge1$ allocations, the corresponding scale is $\min\{\sqrt n,(k/n)^{1/4}\}$. No stationarity, symmetry, recurrence, or moment assumption is used. A smoothed threshold rule in the same class has expected gap $O(\sqrt n\log n)$ up to any fixed polynomial time horizon, so the saturated cycle bound is sharp within the class up to a logarithmic factor. The general inequality also yields a lower bound of order $\sqrt{L/K}$ on the $L\times K$ rectangular torus $C_L\square C_K$; combined with a strategy-independent logarithmic bound, this gives order $\sqrt{L/K}+\log(LK)$. These results separate endpoint-local rules from global-information strategies that achieve polylogarithmic gaps on cycles. All numbered results are verified in Lean.

0.57

Empirical concentration for chains with infinite memory

cs.LG stat.ML ·2026-10-23 ·Pierre Alquier, Paul Doukhan
similarity 0.58
Abstract

Concentration inequalities for time series usually involve unknown quantities measuring dependence. This prevents their direct use as confidence bounds, or as criteria for learning algorithms. Recent works proved empirical concentration inequalities for stationary Markov chains, where the unknown quantities are estimated. We extend this approach beyond the Markov case, by considering stationary chains with infinite memory. We first establish a bounded-differences inequality on bounded Polish metric spaces under a summable Wasserstein contraction condition. We then estimate its dependence coefficients from a single trajectory, using either transition counts when the state space is finite, or derivatives of kernel conditional-density estimates for a continuous state space. We give general error bounds and illustrate their dependence on the memory tail. Finally, a fixed multiplicative safety factor turns these estimators into empirical concentration bounds. While some regularity assumptions are required to make the bounds empirical, our procedure remains fully adaptive in the sense that it does not require the knowledge of the constants involved in these assumptions. The empirical confidence bounds derived from our results are asymptotically as tight as the theoretical ones.

0.14

Steady-State Convergence of Stochastic Approximation

cs.LG stat.MLmath.OCmath.PR ·2026-09-14 ·Yixuan Zhang, Qiaomin Xie
similarity 0.57
Abstract · 56 pages, 7 figures

For constant-stepsize stochastic approximation (SA), the iterates converge in distribution to a stationary law that depends on the stepsize $α.$ Steady-state convergence (SSC) concerns the limit of the scaled stationary distribution as $α\downarrow 0.$ Existing SSC theory requires i.i.d. or additive noise and global differentiability of the mean operator, and yields suboptimal rates. We develop a unified SSC theory for constant-stepsize contractive SA driven by Markovian, multiplicative noise, covering both locally differentiable and locally nondifferentiable mean operators. A key methodological contribution is a multi-step universality framework that progressively reduces the original stochastic recursion to tractable auxiliary dynamics while preserving its steady-state limit. Under local quadratic linearization at the fixed point, we obtain a Gaussian approximation of the scaled steady state at the optimal rate $O(\sqrtα)$ in Wasserstein-2 distance, which further gives finite-time Gaussian approximations for the raw iterates. In the locally nondifferentiable regime, we establish a general SSC result and show that the leading-order asymptotic bias can be of order $\sqrtα$, in contrast to the $α$-order bias in the smooth regime. We apply the theory to Markovian linear SA and asynchronous Q-learning, neither of which is covered by prior results. We further propose a bias-reduction scheme for Q-learning that requires no knowledge of the local smoothness regime, validated by numerical experiments.

0.45

Stochastic Network Speed Scaling with Competitive Ratios Independent of the Network

cs.DS cs.PF ·2026-10-02 ·Yash Khanna
theory similarity 0.56
Abstract · 14 pages, 2 figures, 1 table

In network speed scaling, jobs arrive over time at a network of servers whose speeds can be tuned, every job must be processed by the servers along one of its allowed routes, and the goal is to minimize the total flow time plus the total energy. For stochastic arrivals, the competitive ratio of Vaze and Nair depends on the network, through the lengths of the routes it uses. We show that this dependence can be removed: we give an algorithm, which routes the jobs by solving a convex program and runs every server at a fixed speed, whose competitive ratio depends only on the power functions; for $P(s)=s^2$, it is at most the golden ratio $\varphi\approx1.618$. The key idea is a lower bound on the optimal cost which, like the cost of our algorithm, is a sum over the servers of a function of each server's load, so the analysis reduces to a single server. We also show that the routing rule of Vaze and Nair can be a factor $Ω(L)$ away from optimal, where $L$ is the length of the longest route.

0.31

Dynamic Skill-Based Routing for Call Centers with Transfers: A Value-Based Framework

eess.SY ·2026-10-18 ·Baris Ata, Ebru Kasikaralar
benchmarkcode/data similarity 0.55
Abstract

We consider a multi-class, multi-pool queueing model of a telephone call center in which a service completion does not always end the call. The caller may be transferred to another agent for a second service, so the assignment of an agent to a call affects not only the caller's waiting time but also whether the call is resolved and how much further work it creates. We model these transfers as Markovian routing from original to rework classes, and the system manager dynamically assigns agent pools to classes so as to maximize the value generated by service, net of transfer penalties and waiting and abandonment costs, over a finite horizon. Focusing on the Halfin-Whitt heavy-traffic regime, we derive an approximating Brownian control problem. Its Hamilton-Jacobi-Bellman equation is a semilinear partial differential equation whose dimension equals the number of classes. Building on the deep splitting method of Beck et al. (2021), we develop a simulation-based computational method that approximates the value function and its gradient by neural networks, and we use it to construct an implementable routing policy for the original (prelimit) system. We calibrate the model to publicly available data from a large U.S. bank call center. In all test problems we consider, the proposed policy outperforms the best available benchmark policy we could find.

0.34