Wireless networks without a central controller often decide who transmits through a randomized protocol. Each link repeatedly flips a biased coin to join or leave the set of active transmitters, and it biases the coin by a "weight" computed from its own queue length. This process is a Markov chain over sets of links that can transmit without interfering, and it eventually settles on schedules that favor heavily loaded links. Theory says this reaches full network capacity only if the weights grow extremely slowly in the queue length, for example as $\log\log q$ or roughly $\log q$. The reason is that the chain takes exponentially longer to settle as weights get larger, so it has to keep pace with a moving target. The cost of that slowness is delay. A link holding 2,000 packets looks almost the same to the protocol as one holding 1,000, and when a traffic burst arrives, the weights rise too slowly to clear it quickly.
This note proposes giving each link a machine-learned forecast of its own near-future arrivals and letting that forecast shift the link's weight by a bounded, capped amount. The forecast does not replace the slow queue-based curve. The key observation is that a bounded additive error in the weights costs only a bounded constant in the chain's settling time and in stability. Stability should therefore survive any forecast, however wrong, while a correct forecast lets a link raise its weight before a burst arrives rather than after. The size of the cap is the dial that trades best-case delay (consistency) against worst-case delay (robustness). A local check on whether the forecasts are coming true can shrink the cap online.
Core Claim
Existing learning-augmented algorithms tune how much to trust a prediction for centralized problems with finite costs. Examples are ski rental and job scheduling with a trust parameter in Improving Online Algorithms via ML Predictions, biased update speeds for online covering in The Primal-Dual method for Learning Augmented Algorithms, and ratio-triggered fallback in a single packet switch in Learning-Augmented Online Packet Scheduling with Deadlines. None of them deals with a distributed randomized scheduler whose correctness depends on the chain settling before its parameters move.
The obvious crossover would make the weight curve itself more aggressive when predictions are trusted, say sliding from $\log q$ toward $q$. This proposal argues against that design. The CSMA literature shows that growth faster than logarithmic breaks stability (On the Design of Efficient CSMA Algorithms for Wireless Networks reports $\sqrt{q}$ going unstable at load 0.92). It also shows that settling time is exponential in the largest weight (Distributed Rate Allocation for Wireless Networks). A trusted-but-wrong prediction that switches a link to fast growth would therefore push the chain into exactly the slow-settling regime these papers warn about.
Our claim is different. Predictions should change the weight's timing, not its growth order. Concretely, each link $i$ uses
$$w_i(t) = f\big(q_i(t)\big) + \mathrm{clip}_{[0,B]}\Big(\beta\,\big[f\big(q_i(t)+\hat a_i(t)\big) - f\big(q_i(t)\big)\big]\Big).$$
In this formula, $q_i(t)$ is the link's current queue, $f$ is a slow curve that already guarantees full capacity (such as $\log(1+q)/\log(e+\log(1+q))$ from On the Design of Efficient CSMA Algorithms for Wireless Networks), $\hat a_i(t)$ is the forecast number of arrivals over a short horizon, $\beta$ scales the offset, and $B$ caps it.
The conjectured theorem has two parts. First, for every finite cap $B$ and every forecast sequence, including adversarial ones, the network stays stable for every arrival rate strictly inside capacity; this is stability-robustness. Second, the steady-state backlog under adversarial forecasts exceeds that of plain $f$ by at most a factor growing like $e^{O(B\Delta)}$, where $\Delta$ is the maximum number of interfering neighbors of a link. Both parts have the same source. The chain's equilibrium weights each schedule in proportion to $e^{\sum w_i}$, so a perturbation of at most $B$ per link changes the equilibrium by at most a factor $e^{B\Delta}$ locally. It changes settling time by a similar factor. It never changes how fast weights grow with the queue, which is what the timescale-separation argument actually needs. The design aims for delay-consistency: with accurate forecasts, a link's weight climbs before its backlog does, so the chain has already moved toward the right schedules when the burst lands.
Research Program
The theoretical work adapts the proof of Network adiabatic theorem: an efficient randomized protocol for contention resolution. "Adiabatic" there means that if weights change slowly enough, the chain stays close to its equilibrium; that paper uses this to show the $\log\log$ protocol reaches full capacity. We would carry the bounded offset through that proof as a weight error of at most $B$. This is the kind of imperfection that queue-length schedulers tolerate, because the queue term grows without bound while the error does not. The analysis must handle two issues honestly.
The first is the global maximum-queue estimate. The proofs in Network adiabatic theorem, Randomized scheduling algorithm for queueing networks, and On the Design of Efficient CSMA Algorithms all rely on this network-wide quantity. We will inherit that assumption rather than claim to remove it. The second issue is that the offset can change faster than the chain settles. Our argument is that the chain is then at equilibrium for some offset in $[0,B]$, so it still tracks the queue term to within the bounded error. We will verify this in the proof rather than assume it.
The delay side is harder. We plan a bound in a simple regime with periodic on-off bursts on a fixed conflict graph. The goal is to show that a perfect forecast with horizon $H$ removes the "ramp-up" delay of the slow curve, which scales with the settling time at the new weight level. Everything beyond that regime will be measured rather than proven.
The adaptive-trust component replaces the fixed cap with $B_i(t)$. Link $i$ compares its forecast arrivals with its realized arrivals over the random intervals between its own coin-clock ticks. It halves $B_i$ when the relative error exceeds a threshold and increases it additively otherwise. This is a local analogue of the ratio check in Learning-Augmented Online Packet Scheduling with Deadlines, which needs global knowledge of an optimal schedule. Our check needs only the link's own arrival counts. Stability of the adaptive version follows trivially from the fixed-$B$ result, since the budget never exceeds its maximum. The analysis question is how quickly delay recovers after a forecast failure. For this we use the random-time convergence rates of On Rates of Convergence for Markov Chains under Random Time State Dependent Drift Criteria, which tie convergence speed to the tails of the check intervals. Exponentially distributed clock ticks fall in the geometric-rate case.
The forecasts come from small per-link models trained on arrival histories. Following ATLAS: Alibaba Dataset and Benchmark for Learning-Augmented Scheduling, which found log-domain targets necessary under heavy-tailed workloads and recurrence features responsible for most of the accuracy, we predict log-arrivals and use lagged and periodic features. We also compare the learned forecaster against a moving-average forecaster, to test whether any learned structure matters.
Baselines
The naive reference point is plain queue-weighted CSMA with the $\log\log(q+e)$ curve of Network adiabatic theorem. It shows how large the delay problem is.
The strongest static competitor is the fastest provably stable curve, $\log(1+q)/\log(e+\log(1+q))$, from On the Design of Efficient CSMA Algorithms for Wireless Networks. That paper reports, on the 24-link grid at load 0.85, average queues under 100 packets per link, compared with more than 4,000 for $\log\log$. Our simulator must reproduce this gap before any other comparison counts. To be fair, we will also give this baseline a tuned multiplicative constant on $f$, with the same grid-search budget we spend on $\beta$ and $B$. Otherwise our method would get extra tunable parameters that the baseline lacks.
The strongest heuristic competitor is Hybrid Q-CSMA from Q-CSMA. It runs distributed greedy scheduling below a queue threshold $w_0$ and logarithmic Q-CSMA above it. The paper reports qualitatively low delay near capacity but gives no numbers; no reported result was found on Lacuna for its delay values. We will tune $w_0$ per topology and per trace with the same budget.
The key ablation removes the cap and uses $f(q+\hat a)$ directly. This isolates whether the bound $B$, and not the forecast itself, is what buys robustness. A second ablation replaces the learned forecaster with a moving average, and a third replaces the adaptive budget with a fixed one.
Beating a baseline means lower mean and 99th-percentile delay under accurate forecasts at equal tuning budget. Under adversarial forecasts, our method must stay stable and keep delay within a measured factor of the tuned static curve.
Why not just…?
Why not just tune Hybrid Q-CSMA's threshold? This is the most serious threat. A well-chosen $w_0$ may capture most of the delay gain under stationary traffic. Two things limit it. Its greedy mode achieves only two-thirds of capacity on the 9-link ring (Q-CSMA), and its switch fires only after the queue has already built up. Our experiments separate the two methods by traffic type. If tuned Hybrid Q-CSMA matches us on bursty traces with periodic structure, then foresight adds nothing, and we will report that. We expect an advantage only when bursts are predictable in advance.
Why not just scale up the static log-like curve? A larger constant also makes weights respond faster at every queue length, and it costs no forecasts. The drawback is that it raises the largest weight everywhere, all the time. Settling time grows exponentially in that weight (Distributed Rate Allocation for Wireless Networks), so the scaled curve pays the settling-time price even when no burst is coming. Our offset pays it only when a burst is forecast. The equal-budget tuning of the constant is designed to settle this directly.
Why not just feed the predicted queue into the weight? This is the uncapped ablation. With a wrong but confident forecast, a link's weight becomes unbounded relative to its actual queue. That is the regime that makes faster-than-logarithmic weights unstable (On the Design of Efficient CSMA Algorithms). We expect the ablation to blow up under adversarial forecasts at high load. If it does not, the cap is unnecessary and the theory is too conservative.
Proposed Experiments
Topologies are the 24-link grid, the $10\times10$ grid under both uniform and chessboard traffic from Network adiabatic theorem, and the 9-link ring. We simulate both idealized continuous-time CSMA and the discrete-time Q-CSMA protocol with control slots. Arrival processes include Bernoulli traffic, which is the control case where forecasts carry little signal and we expect no gain. We also drive links with real traces as on-off burst processes: Google Cluster CPU traces as used in Smoothed Online Optimization for Target Tracking, College Message and Brightkite traces as used in Learning-Augmented Online Packet Scheduling with Deadlines, and ATLAS job-arrival timestamps. Each trace is rescaled to loads from 0.5 to 0.95 of capacity.
Forecast quality is varied in a controlled way. We use accurate learned forecasts, forecasts with Gaussian noise of increasing size, forecasts shifted in time (which are brittle under $\ell_1$ error, as the LAP paper notes), and adversarial forecasts that predict bursts on idle links and silence on busy ones. Metrics are mean and 99th-percentile packet delay, time-averaged backlog, and whether queues grow without bound over long runs. Results are plotted as delay against forecast error for each value of $B$, which traces the empirical consistency-robustness curve.
Three checks decide the question. The first is stability: at load 0.92 on the grid with adversarial forecasts, the capped method must stay stable while the uncapped ablation diverges. The second is the robustness factor: the delay penalty under adversarial forecasts should grow roughly exponentially in $B$, consistent with the conjectured $e^{O(B\Delta)}$ factor. The third is the consistency gain: on predictable bursty traces, accurate forecasts should cut 99th-percentile delay below both the tuned log-like curve and tuned Hybrid Q-CSMA, while Bernoulli traffic shows no gain. If the gain appears on Bernoulli traffic too, it comes from the extra weight rather than from foresight, and the method would reduce to a tuned constant.
References
- Improving Online Algorithms via ML Predictions
- The Primal-Dual method for Learning Augmented Algorithms
- Learning-Augmented Online Packet Scheduling with Deadlines
- On the design of efficient CSMA algorithms for wireless networks
- Distributed Rate Allocation for Wireless Networks
- Network adiabatic theorem: an efficient randomized protocol for contention resolution
- Randomized scheduling algorithm for queueing networks
- On Rates of Convergence for Markov Chains Under Random Time State Dependent Drift Criteria
- ATLAS: Alibaba Dataset and Benchmark for Learning-Augmented Scheduling
- Q-CSMA: Queue-Length-Based CSMA/CA Algorithms for Achieving Maximum Throughput and Low Delay in Wireless Networks
- Smoothed Online Optimization for Target Tracking: Robust and Learning-Augmented Algorithms