Finite-Time Queue Peak Laws in Stochastic Networks: Logarithmic Scaling After Geometric Thresholds

Cheng Tang; Hao Liang; Yunzong Xu

arxiv: 2606.18218 · v3 · pith:IZ2H3TLInew · submitted 2026-06-16 · 🧮 math.PR · cs.LG· cs.SY· eess.SY· math.OC· stat.ML

Finite-Time Queue Peak Laws in Stochastic Networks: Logarithmic Scaling After Geometric Thresholds

Hao Liang , Cheng Tang , Yunzong Xu This is my paper

Pith reviewed 2026-07-02 22:26 UTC · model grok-4.3

classification 🧮 math.PR cs.LGcs.SYeess.SYmath.OCstat.ML

keywords finite-time queue peaksstochastic networksgeneralized switchesMaxWeight schedulinglogarithmic scalingsquare-root envelopeinterior slackstate-space collapse

0 comments

The pith

With interior slack, queue peaks in stochastic networks follow square-root growth only up to a geometry threshold then switch to logarithmic scaling.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies finite-horizon peaks of queue lengths in generalized switches where many queues share service resources under policies like MaxWeight. Arrivals can be dependent and history-responsive, but the only requirement is that their conditional means lie inside a fixed contraction of the capacity region. This interior slack changes the peak law: the square-root envelope holds only up to a threshold that depends on network geometry; past that point the running maximum grows logarithmically in the horizon, both with high probability and in expectation. The mechanism is self-normalization of fluctuations by the stabilizing drift in the current queue direction. Matching lower bounds confirm that the logarithmic term and the geometric threshold cannot be removed.

Core claim

Under uniform interior slack the square-root envelope that is sharp without slack persists only up to a geometry-dependent threshold; beyond that threshold the running maximum grows only logarithmically with the horizon, both with high probability and in expectation, because the projected fluctuation scale is normalized by the stabilizing drift scale.

What carries the argument

Self-normalization, in which the projected fluctuation scale in the current queue direction is normalized by the stabilizing drift scale.

If this is right

Capacity geometry stays in the threshold but drops out of the logarithmic coefficient.
When finite-time state-space collapse is available the threshold can be sharpened by local bottleneck geometry.
For generalized input-queued switches the bounds achieve tight logarithmic coefficients.
Matching lower bounds show both the logarithmic term and the geometric threshold are necessary.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Buffer-dimensioning rules could be tightened by switching from square-root to log scaling once the horizon exceeds the threshold.
The same self-normalization idea may apply to other drift-minimizing policies beyond MaxWeight.
In networks with stronger slack the logarithmic regime could dominate even moderate horizons.

Load-bearing premise

The conditional mean arrival vector stays inside a fixed contraction of the capacity region.

What would settle it

Finding a sequence of horizons where the maximum queue length grows faster than logarithmically with high probability under uniform interior slack would disprove the claimed switch in scaling.

Figures

Figures reproduced from arXiv: 2606.18218 by Cheng Tang, Hao Liang, Yunzong Xu.

**Figure 2.** Figure 2: The local geometry behind the two-queue bound. The green triangle is the capacity region, [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗

**Figure 3.** Figure 3: Nonstationary CRP geometry. The nominal point [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗

**Figure 4.** Figure 4: Two-phase behavior of the mean running peak. Top: mean peak with [PITH_FULL_IMAGE:figures/full_fig_p023_4.png] view at source ↗

**Figure 5.** Figure 5: Two-queue example. Global prediction uses Theorem [PITH_FULL_IMAGE:figures/full_fig_p024_5.png] view at source ↗

**Figure 6.** Figure 6: Geometry and variance effects in generalized IQS. [PITH_FULL_IMAGE:figures/full_fig_p025_6.png] view at source ↗

**Figure 7.** Figure 7: Illustrative compatibility graph for the parallel-server model with [PITH_FULL_IMAGE:figures/full_fig_p030_7.png] view at source ↗

read the original abstract

We study finite-horizon queue peaks in generalized switches, a standard stochastic-network model in which many queues share constrained service resources. Arrivals may be dependent, nonstationary, and responsive to the system history; the only load condition is uniform interior slack, meaning the conditional mean arrival vector stays in a fixed contraction of the capacity region. We show that this slack reshapes the finite-time peak law for drift-minimizing scheduling policies such as MaxWeight. The square-root envelope that is sharp without slack persists only up to a geometry-dependent threshold; beyond that threshold, the running maximum grows only logarithmically with the horizon, both with high probability and in expectation. The mechanism is self-normalization: in the current queue direction, the projected fluctuation scale is normalized by the stabilizing drift scale. This removes capacity geometry from the logarithmic coefficient, while geometry remains in the threshold. Matching lower bounds show that both the logarithmic term and a geometric threshold are unavoidable. When finite-time state-space collapse is available, the threshold can be sharpened using local bottleneck geometry. For generalized input-queued switches, we obtain finite-time peak bounds with tight logarithmic coefficients. Simulations illustrate the two-phase envelope, local geometric refinements, and variance-sensitive improvements predicted by the theory.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper derives a two-phase finite-time peak law under uniform interior slack, with square-root growth only up to a geometry-dependent threshold then logarithmic thereafter, via self-normalization.

read the letter

The main thing to know is that under the paper's uniform interior slack condition, the running maximum queue length for drift-minimizing policies like MaxWeight follows the usual square-root envelope only up to a threshold set by the geometry; past that point it grows only logarithmically in the horizon, both in high probability and in expectation. They back this with matching lower bounds and a self-normalization step that removes geometry from the logarithmic coefficient while leaving it in the threshold.

What the work does cleanly is spell out how the slack alone produces this reshaping, plus the refinements available when finite-time state-space collapse holds. For generalized input-queued switches they extract explicit tight logarithmic coefficients. The simulations are described as confirming the two-phase shape, the local geometric sharpening, and some variance-sensitive effects.

The soft spots are the usual ones when only the abstract is in front of you: the actual error terms, the handling of the non-stationary and history-responsive arrivals, and the precise simulation setups are not visible, so the practical tightness of the bounds is hard to judge yet. The load condition is stated plainly as the sole assumption, and the stress-test note finds the argument internally consistent with no extra moment or uniformity requirements slipped in.

This is aimed at people working on stochastic networks and finite-horizon queueing analysis. It has enough new scaling structure and explicit results to deserve a serious referee, even if the proofs will need close checking.

Referee Report

0 major / 3 minor

Summary. The manuscript establishes finite-time laws for the running maximum of queue lengths in generalized switch models under the sole assumption of uniform interior slack. It shows that the peak grows as the square root of time up to a geometry-dependent threshold, after which it transitions to logarithmic growth with the horizon, both with high probability and in expectation, for drift-minimizing policies such as MaxWeight. The mechanism is self-normalization of projected fluctuations by the stabilizing drift. Matching lower bounds are provided, and the threshold can be sharpened using finite-time state-space collapse when available. Specific bounds with tight logarithmic coefficients are obtained for generalized input-queued switches, with simulations illustrating the two-phase envelope and refinements.

Significance. If the derivations hold, the result provides a sharp refinement of transient peak laws in stochastic networks by identifying the transition from square-root to logarithmic scaling induced by uniform interior slack. The self-normalization argument, which removes capacity geometry from the logarithmic coefficient while retaining it in the threshold, is a notable technical contribution. Matching lower bounds and applicability to input-queued switches strengthen the work, as do the simulations validating the predicted envelope and variance-sensitive improvements. This advances performance analysis for finite-horizon behavior under minimal load conditions.

minor comments (3)

The abstract refers to 'generalized input-queued switches' obtaining finite-time peak bounds; the main text should explicitly state in which section or theorem this specialization is derived from the general case.
Simulations are said to illustrate 'local geometric refinements'; a minor clarification on how the plotted thresholds align with the geometry-dependent threshold in the main theorems would improve readability.
The claim of 'tight logarithmic coefficients' for input-queued switches would benefit from a brief comparison in the text to the general logarithmic term derived earlier.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our results on finite-time queue peaks under uniform interior slack, as well as the recommendation for minor revision. The assessment correctly identifies the self-normalization mechanism, the square-root to logarithmic transition, matching lower bounds, and applicability to input-queued switches.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper derives finite-time peak laws for queue maxima under uniform interior slack via self-normalization of projected fluctuations by stabilizing drift, yielding a two-phase envelope with matching lower bounds. No load-bearing step reduces by construction to a fitted parameter, self-definition, or self-citation chain; results are framed as external mathematical bounds plus simulations, with no renaming of known patterns or ansatz smuggling. The argument remains independent of its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the uniform interior slack load condition and standard properties of drift-minimizing policies; no free parameters or invented entities are mentioned in the abstract.

axioms (1)

standard math Standard assumptions from probability theory and stochastic processes for modeling arrivals, services, and stability in queueing networks.
Invoked implicitly to support finite-time analysis and high-probability bounds.

pith-pipeline@v0.9.1-grok · 5770 in / 1178 out tokens · 31334 ms · 2026-07-02T22:26:52.044133+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Bellman-sufficient Information Complexity
cs.LG 2026-06 unverdicted novelty 7.0

Introduces Bellman-sufficient information complexity as a representation-level framework for sequential decision making that unifies upper and lower bounds through a conditional Bellman information-risk sandwich.
Bellman-sufficient Information Complexity
cs.LG 2026-06 unverdicted novelty 6.0

Proposes Bellman-sufficient state representations and information indices Y=χ(Ω) to organize sequential decision making with a conditional Bellman information-risk sandwich providing matching upper and lower complexit...