Hub Caches for Token-Walk Learning on Heavy-Tailed Graphs

In serverless decentralized learning, a group of devices trains one model by passing copies of it to their immediate neighbors, with no central server. One way to do this is to send a few "tokens" around the network. A token is a model copy that hops from device to device and takes a training step on each device's local data. On networks with a few very well-connected devices ("hubs"), a random walk keeps landing on those hubs. This is the friendship paradox: your random neighbor tends to have more friends than you do. We propose to stop treating that bias as a nuisance and build the learning system around it. Each hub keeps a small cache of the tokens it has recently seen. That cache then does three jobs. It lets tokens average with each other without a designated mixing node. It lets a token arriving at a hub be sent as a short log of recent changes instead of a full model. And it lets each device set its own processor speed, transmit power, and bit budget from quantities it can compute alone.

The opportunity is concrete. Token-walk learning already moves an order of magnitude fewer bytes than neighbor-averaging gossip in sparse graphs. On OPT-125M fine-tuning, A Tale of Two Learning Algorithms: Multiple Stream Random Walk and Asynchronous Gossip reports about 50 GB for Multi-Walk against about 600 GB for asynchronous gossip. But that method mixes tokens at a fixed "Node 0", ignores degree structure, sends uncompressed models, and treats computation as a fixed delay. Meanwhile, every energy-aware method that jointly sets quantization, processor frequency, and radio power assumes a star topology with a server. We aim to close both gaps with one mechanism and to say precisely when it should fail.

Core Claim

On graphs with heavy-tailed degrees, one knob sets three quantities at once: how strongly the token walk is biased toward high-degree neighbors. Those quantities are where tokens meet, which devices' data the model over-samples, and which devices bear the energy load. Let token transitions from device $i$ to neighbor $j$ follow $P_{ij} = d_j^{\alpha} / \sum_{k \in N(i)} d_k^{\alpha}$, where $d_j$ is $j$'s degree, $N(i)$ is $i$'s neighbor set, and $\alpha$ is the tilt ($\alpha=0$ is the simple random walk). This walk is reversible with edge weights $(d_i d_j)^{\alpha}$, so its long-run visit frequency is

$$\pi_i \propto d_i^{\alpha} \sum_{k \in N(i)} d_k^{\alpha},$$

which each device can compute from a one-hop query. By Kac's lemma, the expected time between token visits to device $i$ is $1/\pi_i$ (up to the global normalizer, which devices can estimate from observed return times).

The new claim has three parts. First, hubs should cache tokens. Second, a token arriving at a device should be encoded as the quantized changes made since that device last saw it. Third, transmission, compute, and bit-width decisions should be driven by the observed time since the last visit. Under these choices, the friendship paradox's concentration of traffic on hubs becomes cheap, because hubs see tokens often and therefore receive small updates. It also becomes useful, because hubs become decentralized mixing points. The expected payoff is a better accuracy-per-joule frontier than both degree-weighted gossip and uniform token walks, and the gain should grow with degree variance. On graphs without hubs, the same theory predicts no gain, and we will check that prediction directly.

Research Program

Encoding. The first piece is the encoding, which is the key ingredient. Each token carries a version counter and a short append-only log of its recent quantized local updates. Each update is quantized once by the device that produced it, using error feedback. The token's canonical state is defined as the reconstruction, so every holder agrees exactly on what the token is. When the token arrives at device $j$, which last saw it $k$ hops ago, the sender ships only the last $k$ log entries. When $k$ is large enough that the log would cost more than a quantized full model, the sender ships the full model instead.

For hubs, $k$ is small, because the friendship paradox makes return times short. The bit-width of each logged update follows two existing ideas. One is a loss-driven schedule in the style of Adaptive Quantization of Model Updates for Communication-Efficient Federated Learning, which grows the number of quantization levels roughly as $\sqrt{f(w_0)/f(w_k)}$. The other is the range-shrinking rule of Fast Convergence Rates of Distributed Subgradient Methods With Adaptive Quantization and Progressive quantization in distributed average consensus. That rule shrinks the quantization interval in step with the learning rate, which removes the accuracy floor. We reuse these schedules. What we add is the visit-dependent choice between log and full model, which ties bit cost to network position. This is quantization that depends on topology, and none of the cited adaptive schemes conditions on network structure.

Mixing. The second piece replaces Node 0 with hub caches. A device that holds cached copies of other tokens averages the arriving token with them, weighted by staleness. This turns the "breadcrumbs" of Multiple Random Walks to Uncover Short Paths in Power Law Networks from a crawling device into a mixing device. That paper showed that degree-biased walkers intersect after visiting only 1–2.5% of nodes in power-law graphs. Here that fast intersection means tokens mix quickly.

Two prior results pull in opposite directions on whether hubs help. The effect of network topologies on fully decentralized learning: a preliminary investigation found that poorly informed hubs "drag" their neighbors and dilute rare knowledge. Topology-Aware Knowledge Propagation in Decentralized Learning found that hubs act as super-spreaders. We address the dragging risk in two ways. A hub never trains a cached copy; it only stores and averages copies. And staleness weights bound how much an old cached copy can pull an arriving token.

Unbiasedness. Because a tilted walk over-samples some devices' data, the step taken at device $i$ is scaled by $1/(n\pi_i)$, where $n$ is the number of devices. This makes the expected update equal the global average gradient. With heavy tails, this correction inflates the variance of steps taken at rarely visited leaves. That inflation is exactly why $\alpha$ should have an interior optimum. We will derive a convergence bound for the convex case that exposes three terms: mixing speed (better with larger $\alpha$), importance-weight variance (worse with larger $\alpha$), and the quantization error from logs of length $1/\pi_i$. The bound will separate the i.i.d. regime of Beyond spectral gap: the role of the topology in decentralized learning from the non-i.i.d. regime that paper leaves open. For deep networks, we will check empirically whether the predicted optimum for $\alpha$ holds.

Resources. The third piece is per-device resource control. We adapt the drift-plus-penalty method of Lyapunov-Based Optimization of Edge Resources for Energy-Efficient Adaptive Federated Learning. That method converts long-term energy budgets into per-slot decisions using "virtual queues" that track how far over budget a device is running. It was designed for a star topology, so we move it to each device. On each token visit, device $i$ chooses four things: its processor frequency (computation power scales as frequency cubed), its transmit power to the next device, the bit-width of the update it logs, and whether to compute at all or only average and forward. These choices trade its energy virtual queue against expected training progress.

The point of the topology is that the expected load on each device is $\pi_i$ times per-visit cost, which is known locally. No device needs global coordination. The only shared quantity is $\alpha$, which is fixed per deployment. Hubs that are running hot can forward tokens without computing, which caps the battery drain that the friendship paradox would otherwise concentrate on them.

Baselines

Naive reference. The naive reference is asynchronous decentralized parallel SGD (AD-PSGD, i.e., pairwise gossip averaging) with fixed 4-bit quantization of exchanged models. Every device runs at maximum processor frequency with fixed transmit power. This is what a practitioner would deploy without thinking about topology. Adaptive Quantization of Model Updates for Communication-Efficient Federated Learning gives a reference point for how badly fixed low precision can fail: on ResNet-18 CIFAR-10, fixed 2-bit needed 1.8 Gb to reach loss 0.02 against 0.3 Gb adaptive, though in a centralized setting.

Strongest walk-based competitor. This is Multi-Walk from A Tale of Two Learning Algorithms, run with its Node 0 mixing and simple random-walk transitions. We upgrade it with AdaQuantFL-scheduled quantization of full-model transfers and the same per-device Lyapunov controller we use, so that the only remaining differences are tilt, hub caches, and log encoding. Its reported number is about 50 GB of transmitted data against about 600 GB for gossip on OPT-125M/MultiNLI. For ResNet-20 on CIFAR-10, the file gives only a qualitative statement that Multi-Walk converged faster per iteration on cycles; there is no reported scalar result on Lacuna for that setting.

Strongest gossip competitor. This is degree-centrality topology-aware aggregation from Topology-Aware Knowledge Propagation in Decentralized Learning, with softmax-tempered degree weights. Degree is locally computable, so this baseline does not suffer from the global-knowledge problem that affects betweenness centrality. It is equipped with the same adaptive quantization and controller. Its reported result is OOD accuracy of 42% against a 20% topology-unaware baseline, and 123% average OOD improvement.

Hierarchical competitor. This baseline elects hubs as cluster servers and runs QCCF from Energy-Efficient Wireless Federated Learning via Doubly Adaptive Quantization within each cluster, with periodic hub-to-hub gossip. QCCF reports up to 48.21% and 35.42% energy savings over its baselines on FEMNIST and CIFAR-10. The Lyapunov AFL paper reports 30–50% power reduction.

Fair comparison and ablations. All methods share the same graph, data partition, model, local step count per visit, a simulated energy model (cubic compute power, Shannon-rate links with Rayleigh fading), and an equal hyperparameter search budget (the same number of trials over learning rate, bit schedule, and either $\alpha$ or temperature). The ablations isolate each ingredient: $\alpha=0$ with everything else kept; tilt without hub caches, using Node 0 mixing instead; hub caches without log encoding, so full models are always sent; and log encoding without the visit-dependent choice between log and full model.

What counts as beating them. We count it as a win if, at matched test accuracy, the proposal uses at least 1.5× less total energy and keeps the most-loaded device's energy within its budget on Barabási–Albert graphs, while matching or exceeding the Topology-Aware OOD accuracy under that paper's protocol.

Why not just…?

Why not just use degree-weighted gossip, since degree is local anyway? This is a real threat. The global-knowledge objection to Topology-Aware Knowledge Propagation in Decentralized Learning applies to betweenness centrality, not to degree. Our case rests on communication volume. Gossip makes every hub exchange with many neighbors each round, which is exactly the traffic pattern that cost 12× more bytes than walks in A Tale of Two Learning Algorithms. That measurement, however, was on cycles and complete graphs, not scale-free ones. If degree-weighted gossip with adaptive quantization matches our accuracy-per-joule curve on Barabási–Albert graphs, the walk machinery is unjustified, and the head-to-head comparison is designed to show this outcome if it holds.

Why not just make hubs local servers and run existing star-topology energy optimization? On scale-free graphs this is the most natural engineering answer, and QCCF's per-cluster savings are strong. It falls short in two ways. It creates per-cluster single points of failure. And between clusters it reintroduces the hub-dominated averaging that The effect of network topologies on fully decentralized learning showed causes dragging and accuracy ceilings, about 25% in its community-structured tests. We will test the hierarchical baseline on stochastic-block-model graphs and under hub churn, where we expect it to degrade. If it does not degrade, we will report that.

Why not just run Multi-Walk with a better quantizer? This is exactly our $\alpha=0$ ablation combined with the no-cache ablation. If the tilt and caches add nothing over Multi-Walk plus AdaQuantFL, the friendship-paradox component is decorative. Our prediction is that the gap is large when degree variance is high and near zero on low-variance graphs. That pattern would identify the mechanism.

Why not just flatten the walk to uniform visits to avoid importance-weight variance? A Metropolis–Hastings walk visits every device equally often and needs no step-size correction. But it discards the fast token intersections that make cache mixing work. The $\alpha$ sweep, which includes negative values, measures this trade directly.

Decisive Experiments

We use four learning tasks. ResNet-20 on CIFAR-10 with Dirichlet non-i.i.d. partitions follows the Multi-Walk setup. FEMNIST with natural per-writer splits follows QCCF. The CIFAR-10 OOD protocol follows Topology-Aware aggregation. OPT-125M on MultiNLI measures bytes at language-model scale. Graphs have 128–256 devices: Barabási–Albert graphs; configuration-model graphs with power-law exponents 2.1, 2.5, and 3.0; and snowball subgraphs of Flickr, LiveJournal, and Enron, as used in Multiple Random Walks to Uncover Short Paths in Power Law Networks, after checking that each subgraph retains high degree variance.

The decisive falsification check uses two hub-free controls: a Power Grid subgraph, on which RWSP failed, and the 4×8 torus from Beyond spectral gap. The theory says the advantage over the $\alpha=0$ ablation should shrink monotonically with degree variance and vanish on these controls. A gain on the torus would mean something other than the claimed mechanism is at work.

Three further checks test the mechanism directly. Measured per-visit bits at each device should track the logarithm of its observed return time. The best $\alpha$ should lie strictly inside the sweep range and shift toward smaller values as the non-i.i.d. skew increases, as the variance term predicts. Per-device energy distributions should show that the controller's forward-without-compute option keeps hubs within budget without lowering final accuracy.

We report test accuracy against total bits, total joules, the maximum energy spent by any single device, and wall-clock time to target. Each result is averaged over five seeds with confidence intervals. Hub-cache memory is reported alongside, because caching several OPT-125M copies at a hub is a real cost.